Due-window assignment problems with unit-time jobs

摘要

We study a class of due-window assignment problems. The objective is to find the job sequence and the window starting time and size, such that the total cost of earliness, tardiness and due-window is minimized. The study assumes unit-time jobs, and considers settings of a single machine and of parallel identical machines. Both the due-window starting time and size are decision variables. For the single machine setting, we study a complete set of problems consisting of all possible combinations of the decision variables and four cost factors (earliness, tardiness, due-window size and due-window starting time). For parallel identical machines, we study a complete set of problems consisting of all possible combinations of the decision variables and three cost factors (earliness, tardiness and due-window size). All the problems are shown to be solvable in no more than O(n3) time, where n is the number of jobs.