Single Machine Scheduling Problem With Due Date Assignment

Scheduling problem is a kind of very important combinatorial optimizationproblems. We discuss some single machine scheduling problems with due datesassignment in this paper, the contex is as following:The first chapter mainly introduces some background knowledges of thescheduling problems, the research status and the main research content of this paper.The second chapter considers the single machine scheduling problems with due datesin which the jobs have controllable processing times, the objection is to minimize thetotal cost concluding earliness, tardiness, due dates and resource consumption. Wedetermine the optimal resource allocation by using the properties of the optimalsequence, and we combine the effects of learning with controllable processing times,processing time is a linear resource function or convex resource function, we showthat the problem can be solved in polynomial time. The third chapter considers themultiple common due dates assignment and single machine scheduling with adeteriorating maintenance activity. The maintenance duration is a linear functionabout its starting time, the objective is to find the optimal due dates, the optimalmaintenance position, and the optimal job sequence, we design a polynomial timealgorithm, and discuss the special case of the problem. The fourth chapter introducesthe single machine scheduling problems with multiple common due dates, we proveseveral important properties, the objective function include earliness, tardiness, thethe sizes of due dates and starting time of due dates, we give an efficient algorithmand analyze the computational complexity of this algorithm. The last section containssome conclusions.