Summary of several job scheduling problems

* Flow scheduling （ Dynamic programming ）

set up T(S,t) Indicates the completion of the job set S The best time ,t Means to start doing S When working in , machine M2 also t Time （t It's a time period ） Come out free
The optimal value of flow shop scheduling is T(N,0) .0 When you start to do your first homework ,M2 Just idle .

This formula means ：
Suppose you do your homework first i , It must be in M1 Flower on a1 Time for , As long as one homework is M1 The complete , You can start doing other homework , Do it here N Remove the job i The time spent on your homework is

Start removing i When I do my homework ,M2 Need to wait bi Time is free
The whole formula i Take 1~n, Take and use T(N,0) The smallest

Extended to the general situation , That is, when doing any homework ：

Items here i It means the first homework to be done , But when you have to do other homework ,M2 The time period from waiting to idle has changed
t: Start doing S During homework ,M2 Still have to wait t The time period is free
When ai>t, Get started S-{i} Time to wait bi Period of time M2 To be free ：

When ai<t, Get started S-{i} Time to wait t-ai+bi Period of time M2 To be free :
Calculate the final time required ：

（ The illustration above ： stay M1 or M2 The working time required on the machine / The moment after completion ）

* Multi machine scheduling problem （ Greedy Algorithm ）

* Batch job scheduling ( backtracking )

Batch job scheduling deals with the same problem as flow job scheduling , All are n Homework ,m Taiwan machine , Every job must be done on the machine first 1 Processing on the machine 2 Top processing , But batch job scheduling requires that all jobs be on the machine 2 The minimum sum of the last completion time .

Algorithm ideas ：
example ：

The procedure is as follows ：
The following procedure is in Flow() Internally defined objects , Open up space , initialization , Destroy space ：

In the above example ：

The full arrangement here is not a dictionary order , For the reasons, please refer to The total permutation problem