Container Scheduling Problem Of Parallel Machine Scheduling Algorithm Research

This paper considers container scheduling problem. Since the real problem is quite complex, we simplify the problem through making reasonable assumptions and convert it into parallel machine scheduling problem with objective of minimizing the make span. Based on the characteristics of the problem and by improving existing scheduling algorithms, we bring up three approximate algorithms. This research has several contributions as flow:1, For the container scheduling problem with possible combination of jobs, we equally convert it into parallel machine scheduling problem of Pm‖Cmax and put forward approximate algorithm A and prove that it has a worst case competitive ratio of 4/3-1/3K(K≥2) and the computational complexity is O(n3+nlogn). The limitation of algorithm A is when K≥t+1 the solution can be improved through splitting of dual command jobs.2, As mentioned in algorithm A, when K≥t+1 the solution can be improved through splitting of jobs, so we put forward the approximate algorithm B with computational complexity of O(n3+nlogn+K) and prove that solution of algorithm B is always no worse than algorithm A, namely CmaxAPB