Due-Window Assignment Scheduling Problems with Position-Dependent Weights, Truncated Learning Effects and Past-Sequence-Dependent Setup-Times

This paper addresses single-machine due-window assignment scheduling with truncated learning effects and past-sequence-dependent setup times. In practical production systems, truncated learning effects capture the ceiling of skill improvement, past-sequence-dependent setup times reflect sequence-dependent switching efforts, and position-dependent weights allow varying importance across job positions. The due-window assignment includes the common, slack, and different assignments. The objective cost is the minimum of the weighted sum of earliness and tardiness, the number of early and tardy jobs, due-window cost, and the completion time. In which the weights are position-dependent. For the common and slack due-window assignments, several optimal structural properties are established. Based on these, the optimal schedule can be derived by solving a series of assignment problems, i.e., the problems can be solved in polynomial time O(n5), where n is the number of jobs. Under the common, slack, and different assignments without the number of early and tardy jobs cost, the optimal schedule of the problems can be obtained from an assignment problem, i.e., the problems can be solved in O(n3) time. In addition, an extension of the job-dependent processing times is given. This study extends existing research models in this domain and proposes polynomial-time algorithms that guarantee optimal solutions for minimizing the objective cost function. The proposed approach not only advances scheduling theory by handling multiple realistic constraints simultaneously but also offers a practical decision-making tool for just-in-time production systems. The algorithms are tested numerically and compared with simulated annealing algorithm and tabu search algorithm.