Bi-criterion single-machine scheduling and due-window assignment with common flow allowances and resource-dependent processing times

Abstract

This paper addresses single-machine scheduling and due-window assignment with common flow allowances and resource-dependent processing times. Due-window assignment with common flow allowances means that each job has a job-dependent due window, the start time and finish time of which are equal to its actual processing time plus individual job-independent parameters shared by all the jobs, respectively. The processing time of each job can be controlled by extra resource allocation as a linear function of the amount of a common continuously divisible resource allocated to the job. Two criteria are considered, where one criterion is an integrated cost consisting of job earliness, weighted number of tardy jobs, and due-window assignment cost, while the other criterion is the resource consumption cost. Four different models are considered for treating the two criteria. It is shown that the problem under the model where the two criteria are integrated into a single criterion is polynomially solvable, while the problems under the other three models are all NP-hard and an optimal solution procedure is developed for them. Two polynomially solvable cases are also identified and investigated. Finally, numerical studies with randomly generated instances are conducted to assess the performance of the proposed algorithms.

Keywords:

• scheduling
• due-window assignment
• controllable processing times
• resource allocation

Acknowledgements

The authors thank the Editors-in-Chief, an Associate Editor, and anonymous referees for their helpful comments on earlier versions of this paper. This paper was supported in part by the National Natural Science Foundation of China (Nos. 11561036, 71501024, 71301022); in part by the MOST of Taiwan under grant numbers NSC 102-2221-E-035-070-MY3 and MOST 103-2410-H-035-022-MY2; and Cheng was supported in part by The Hong Kong Polytechnic University under the Fung You King-Wing Hang Bank Endowed Professorship in Business Administration.