The Scheduling Problem With Setup Times

The scheduling problem with setup times has very important application significance. In this paper, we discuss the scheduling problem with setup times on single machine and parallel machines respectively. At first, we prove the schedulingproblem with general constraint 1|s_ij|∑w_jC_j is NP-Hard. And then we give a polynomial algorithm for the problem 1|s_ij,chains |∑w_jC_j, and the complexityisO(nlogn). Consider the problem 1|s_ij, outtree |∑w_jC_j , we use the method of the maximal family tree to solve the problem when the jobs do not setup at the same time, and give a polynomial algorithm which complexity is O(n²), when the jobs can setup at the same time we give a heuristic algorithm which complexity is O(n² logn). At last we transform the problem P_m | s_ij |∑w_jC_j which is NP-Hardinto an integer program, and design a column generation algorithm about LMP, combine with the Dantzig-Wolfe decomposition technology and use the Dynamic programming to solve the problem.