Common Time Windows Stand-alone Unit Processing Time Packet Scheduling Problem

This paper studies the unrestricted case of common due window scheduling problems within the just-in-time window concept on a single machine. We introduce basic notions of due dates scheduling problem first, and summarize different models and properties of this scheduling problem.In Chapter 2, first, we introduce the background of the common due window scheduling problem. Then we construct a new model of this scheduling problem, in which all the jobs haveunit process time. Jobs belong to mutually exclusive families, and a setup task 5, is required whenthe first job of family F_i to be processed. Jobs that are completed within the due window incur nopenalty, and the earliness and tardiness penalty factors of jobs are arbitrary. The size of the common due window is always a decision variable.In Chapter 3, we analysis the dominance properties of the model. Then we show that the problem of this model is NP-Complete.In Chapter 4, we provide a linear time solvable case of the model and present a polynomial optimal algorithm for this special case.