Association Journal of CSIAM
Supervised by Ministry of Education of PRC
Sponsored by Xi'an Jiaotong University
ISSN 1005-3085  CN 61-1269/O1

Chinese Journal of Engineering Mathematics ›› 2024, Vol. 41 ›› Issue (5): 947-961.doi: 10.3969/j.issn.1005-3085.2024.05.011

Previous Articles     Next Articles

Due Window Assignment Scheduling Problems with Position-dependent Weights on a Single-machine

ZHAO Shuang   

  1. Department of Basic, Shenyang Sport University, Shenyang 110102
  • Received:2023-07-05 Accepted:2024-04-14 Online:2024-10-15
  • Supported by:
    The Science Research Foundation of Educational Department of Liaoning Province (JYTMS20231334).

Abstract:

The single-machine scheduling problems of due window assignment with position-dependent weights are investigated with the aim of minimizing the total weighted sum of the starting time, the size of due window and total tardiness of  due window in a just-in-time environment. The goal is to find the optimal job processing sequence and due window starting time $d_k^1$ (finishing time $d_k^2$). Under common, slack and different due window assignments, the corresponding optimal properties are obtained from the theoretical analysis, it is proved that the problems can be solved in polynomial-time. For the common and slack due window assignments, the time complexity is $O(n^2 \log n)$, while the different due window scheduling problem can be solved in $O(n \log n)$ time, where $n$ is the number of given jobs.

Key words: scheduling, position-dependent weights, single-machine, due window assignment, tardiness

CLC Number: