Single-machine common/slack due window assignment problems with linear decreasing processing times

ABSTRACT

This paper studies linear non-increasing processing times and the common/slack due window assignment problems on a single machine, where the actual processing time of a job is a linear non-increasing function of its starting time. The aim is to minimize the sum of the earliness cost, tardiness cost, due window location and due window size. Some optimality results are discussed for the common/slack due window assignment problems and two O(n log n) time algorithms are presented to solve the two problems. Finally, two examples are provided to illustrate the correctness of the corresponding algorithms.

KEYWORDS:

• Scheduling
• single machine
• due window assignment

Disclosure statement

The authors declare that there is no conflict of interests regarding the publication of this paper. This article does not contain any studies with human participants or animals performed by any of the authors.

Additional information

Funding

This work was partly supported by the National Natural Science Foundation of China [number 11401065, 11571321] and by the Nature Science Foundation of Chongqing [number cstc2014jcyjA00003]. This paper was supported in part by the Ministry of Science Technology (MOST) of Taiwan [grant numbersMOST 105-2221-E-035-053-MY3,MOST 103-2410-H-035-022-MY2 and MOST 105-2816-H-035-001].