Flowshop scheduling

flow shop scheduling

1. Flow shop scheduling By - Kunal Goswami Mentor – Joy Chandra Mukherjee 1

2. Content : 2

3. 3

4. Definition Flow shop scheduling problems, are a class of  scheduling  problems with a  workshop  in which the flow control shall enable an appropriate sequencing for each job and for processing on a set of  machines  or with other  resources  1,2,...,m in compliance with given processing orders . For an operating system – we have many task to be done . Especially the maintaining of a continuous flow of processing tasks is desired with a minimum of  idle time  and a minimum of  waiting time . 4

5. 5

6. Example Practical application : As we have seen strict order of all operations to be performed on all jobs. Flow shop scheduling may apply as well to  production  facilities as to  computing  designs . It is used in processing industry where a strict order of production should be done In can be used in construction work. In medical observation In space technology, agricultural processing basically in every ( multiprograming + strict order job). 6

7. Application It works in following case in steps : we should have multiprogramming environment input and then executed Job queued for O/P O/P printed/used Suppose there are 1 to n job and there are m processor and we have some more information like for task T 3i for processor 3. And it takes t j time . Note - m >= n No more then 1 task for any processor at a time. N jobs requiring m tasks and each to be scheduled in m processor. 7

8. Application So in diagram view situation is like this. Assume we have 4 jobs and each jobs can have 5 tasks. Jobs J 1 J 2 J 3 J 4 Tasks t 1 t 2 t 3 t 4 t 5 3 1 4 2 2 2 3 2 2 1 4 2 1 1 1 3 2 1 8

9. Useful data : The finish time of f i (S) of job i is the time at which all task of job i has been completed in schedule S. The finish time F(S) of a schedule S is : F(S ) = max {f i (S)} The mean flow time MFT(S) is : MFT(S ) = (1/n ). ∑ f i (S) We try to get optimal finish time i.e. minimal finish time . 9

10. 10

11. Above scheduling problem is done by two method Two possible solution : i ) pre-emptive ii) non preemptive. 11

12. pre-emptive Job In it we do permits preemption (halting) of tasks, from a  cooperative multitasking system wherein processes/tasks must be explicitly programmed to  yield  when they do not need system resources . Rules : t ji cannot start unit t j-1,i finishes. Task t i of any job will go to processor i only. 12

13. Example Two jobs (J1,J2) have to be scheduled on two processors. Generate a preemptive schedule. The following matrix give the task times : So, we have 2 jobs with 3 task. J1 J2 13

14. Example First task T1 is coming from two jobs we have. t 11 = 2 and t 12 = 0 Both will be processed sequentially ; all task-1 will complete in 2 sec. 14

15. Example Now Task-2 comes ; T 21 = 3 and T 22 = 3 Task-2 of Job-1 cannot start as it’s first Task-1 needed to be completed. So Task-2 of Job-2 starts. 15

16. Example Now Task-3 comes ; T 3 1 = 5 and T 3 2 = 2 Task-3 of Job-1 cannot start as it’s first Task-2 needed to be completed. So is Task-3 of Job-2 which require Task-2 to complete. 16

17. Example Finish time = Max (F 1 , F 2 ) = max (5,11) = 11 5 and 11 are finish time of respective jobs. Mean flow time = ½ .(5+11) = 8 17

18. Example ii) pre-emptive Job Preemptive Scheduling  is a CPU  scheduling  technique that works by dividing time slots of CPU to a given process. When the burst time of the process is greater than CPU cycle, it is placed back into the ready queue and will execute in the next chance. This  scheduling  is used when the process switch to ready state . Rules : t ji cannot start unit t j-1,i finishes. Task t i of any job will go to processor i only. 18

19. Example Same Job case. Two jobs (J1,J2) have to be scheduled on three processors. Generate a preemptive schedule. The following matrix give the task times : So, we have 2 jobs with 3 task. J1 J2 19

20. Example First task T1 is coming from two jobs we have. t 11 = 2 and t 12 = 0 , It donot have any conflict job in machine. So execute normally. 20

21. Example Task T2 comes. t 21 = 3 and t 22 = 3 , t 21 , t 22 comes. As t 11 not complete. So t 21 goes into queue. And t 22 starts . After t 22 finishes t 21 again complete it’s remaining cycle. 21

22. Example Task-3 comes. t 3 1 = 5 and t 3 2 = 2 , t 31 , t 32 comes. As t 21 not complete. So t 31 goes into queue. Also same with t 32 . t 31 starts after 5 unit time. Then t 32 completes. 22

23. Example Finish time = Max (F 1 , F 2 ) = max (10,12) = 12 10 and 12 are finish time of respective jobs. Mean flow time = ½ .(10+12) = 11 23

24. 24

25. Algorithms The machine sequence of all jobs is the same. The problem is to find the job sequences on the machines which minimize the makespan , i.e . the maximum of the completion times of all tasks. It is similar to 2-machine problem with 2 machines to solve different burst jobs . It is well known that in case of real time situations - the problem is NP-hard. There are some optimized algorithms which uses Dynamic algorithm, Branch and Bound and Heuristic algorithm such as genetic algorithm. 25

26. Algorithms Popular algorithms are : Johnson algorithm – nlogn GS algorithm (Gonzalez and sahni ) Genetic algorithm n.Logn is most optimized solution for finite no. of tasks . We will see Johnson algorithm. 26

27. Algorithms Johnson's Algorithm for 2 machine Step 1 : Form set1 containing all the jobs with p 1j  < p 2j -- ( nlogn ) Step 2 : Form set2 containing all the jobs with p 1j  > p 2j , the jobs with p 1j =p 2j  may be put in either set . -- (n) Step 3 : Form the sequence as follows: (i) The job in set1 go first in the sequence and they go in increasing order of p 1j (SPT ) – shortest process time -- O.(c) (ii) The jobs in set2 follow in decreasing order of p 2j  (LPT). Ties are broken arbitrarily . – longest process time -- O.(c) 27

28. Example Let’s try Johnson's algorithm in our example : We remember it had took us 11 unit for non-preemptive and 12 unit for pre-emptive scheduling using naive process. Our job sequence was : 28 J1 J2

29. Example t1 t2 t3 J1 2 3 5 J2 0 3 2 step 1 – find least among all is ans. cut that column and put in array from left or right according to job1 or job2. 0 task is of J2. So choose from right 29 J1 J2

30. Example t2 t3 (task-1 removed) J1 3 5 J2 3 2 step 1 – find least among all now 2 is ans. cut that column and put in array from left or right according to job1 or job2. 0 task is of J2. So choose from right 30 J1 J2

31. Example t2 (task-3 removed) J1 3 J2 3 step 1 – find least among all now 3 is ans. cut that column and put in array from left or right according to job1 or job2. 0 task is of J2. So choose from right 31 J1 J2

32. Example Above is job sequence for algorithm Now make table including 2 machines So, 10 is execution time of give sequence of task using johnson algorithm which is better from earlier. 32 J1 J2

33. 33

34. Conclusion We got to know about popular scheduling algorithm of tasks in multiprogramming environment. A lot of work is being done in GS and genetic algorithm. Also it is tried with many other field then scheduling. 34

35. 35

36. Reference https:// en.wikipedia.org/wiki/Flow_shop_scheduling https:// www.youtube.com/watch?v=R08ql752oL0 https:// www.sciencedirect.com/science/article/abs/pii/S0360835299000236 https://www.sciencedirect.com/science/article/pii/S1474667015357499#:~:text=Johnson'%20algorithm%20(JA)%20is,algorithms%20for%20more%20general%20cases . 36

37. 37