Single-machine scheduling problems with past-sequence-dependent delivery times and position-dependent processing times

Abstract

This paper considers single-machine scheduling problems with job delivery times where the actual job processing time of a job is defined by a function dependent on its position in a schedule. We assume that the job delivery time is proportional to the job waiting time. We investigate the minimization problems of the sum of earliness, tardiness, and due-window-related cost, the total absolute differences in completion times, and the total absolute differences in waiting times on a single-machine setting. The polynomial time algorithms are proposed to optimally solve the above objective functions. We also investigate some special cases of the problem under study and show that they can be optimally solved by lower order algorithms.

Keywords:

• scheduling
• position-dependent processing times
• past-sequence-dependent delivery times
• due-window assignment
• total absolute differences in completion times
• total absolute differences in waiting times

Acknowledgements

We thank the Editor and three anonymous reviewers for their helpful comments and suggestions on an earlier version of the paper. This research was supported in part by the National Science Council of Taiwan, Republic of China, under grant numbers NSC 99-2221-E-150-034-MY2 and NSC 100-2221-E-252-002-MY2.