The Due Window Assignment Problems with Deteriorating Job and Delivery Time

This paper considers the single machine scheduling problem with due window, delivery time and deteriorating job, whose goal is to minimize the window location, window size, earliness and tardiness. Common due window and slack due window are considered. The delivery time depends on the actual processing time of past sequences. The actual processing time of the job is an increasing function of the start time. Based on the small perturbations technique and adjacent exchange technique, we obtain the propositions of the problems. For common and slack due window assignment, we prove that the two objective functions are polynomial time solvable in O(nlogn) time. We propose the corresponding algorithms to obtain the optimal sequence, window location and window size.

Automated summary

This paper discusses the scheduling problem for a single machine, taking into account due window, delivery time, and deteriorating jobs. The objective is to minimize the window location, window size, earliness, and tardiness. Both common due window and slack due window are considered. The delivery time depends on the actual processing time of previous sequences, which is an increasing function of the start time. By utilizing small perturbations and adjacent exchange techniques, propositions for the problems are obtained. Polynomial time solvability in O(nlogn) time is proven for both common and slack due window assignment. The paper also proposes algorithms to obtain the optimal sequence, window location, and window size.