Research on single-machine scheduling with position-dependent weights and past-sequence-dependent delivery times

This article studies scheduling problems with past-sequence-dependent delivery times (denoted by psddt) on a single-machine, i.e., the delivery time of a job depends on its waiting time of processing. We prove that the total (discounted) weighted completion time minimization can be solved in O(n log n) time, where n is the number of jobs, and the weight is a position-dependent weight. For common (denoted by con) and slack (denoted by slk) due-date assignment and position-dependent weights (denoted by pdw), we prove that an objective cost minimization is solvable in O(n log n) time. The model (i.e., psddt and pdw) can also be extended to position-dependent (time-dependent) processing times.

Automated summary

This article studies scheduling problems with past-sequence-dependent delivery times on a single-machine and proves that certain objective cost minimization can be solved in O(n log n) time. The model can also be extended to position-dependent processing times.