Study On Some Single-machine Scheduling Problems With Setup Times

Scheduling problem is one of the important combinatorial optimization problems.This thesis discusses the single machine scheduling problem with installation time, grouptechnology (GT), resource constraints and a variable processing time. This thesis consistsof seven chapters. Chapter1introduces some background information of the schedulingproblem. Chapter2discusses some scheduling problems with setup times in whichobjective functions are the maximum completion time, total completion time and the totalabsolute deviation of completion time respectively. In this paper polynomial algorithms aregiven for optimally solving problems1|chains,spsd|Cmax,1|spsd(b1,L,bn)|TCand1|spsd(b1,Lbn)|TADC. In chapter3the single machine scheduling problem with grouptechnology and psd installation times1|s psd,GT|∑Cjis discussed, and a polynomialtime algorithm is described. Chapter4concerns the environment with setup time andlearning effect, and the objective is to minimize the total lateness, total tardiness and themaximum lateness respectively. Under certain conditions, polynomial time algorithms foroptimally solving problems1|LE,psd|∑Lj,1|LE,psd|∑Tjand1|LE,psd|Lmaxarepresented. Chapter5takes into account resource constraints and a deteriorating effect in asingle machine scheduling with GT. An optimal solution procedure for problem1|si=f(u i), G,pij(a+bt),∑ui≤U|Cmaxis given. In chapter6scheduling problem1|chains,spsd|Cmaxwith chain constraints and psd installation times is discussed and apolynomial time algorithm for optimal solution is proposed. Chapter7gives summary ofthe thesis, and further research work in future is suggested.