The Two Single-Machine Scheduling Problems with Slack Due Date to Minimize Total Early Work and Late Work

doi:10.1007/s40305-023-00528-7

Abstract

Abstract: This paper considers the single-machine scheduling problem with slack due date. The decision needs to determine the optimal job sequence when the due date of jobs is determined. Slack due date means that the due date is equal to its processing time plus a constant, where the constant is the decision variable. The aim is to assign the slack due date and minimize the objective function. The objective function includes the early work, late work and slack due dates. In this paper, we discuss two problems with slack due date. For the first problem, we address the range of slack due date by cost coefficients, and design a dynamic programming algorithm to solve the proposed problem. It is proved that the optimal solution can be obtained in O(n³P³ log n) time. For the latter problem, we address the time-window assignment problem, and present a dynamic programming algorithm by determining the rang of due date of time window in O(n⁴P⁵ log n(1 + P)) time. Finally, a numerical example is presented to illustrate the feasibility of these algorithms.

Key words: Scheduling, Slack due dates, Time window assignment, Early work, Late work

CLC Number:

90B35
90C27

Xin-Gong Zhang, Xiao-Min Tang. The Two Single-Machine Scheduling Problems with Slack Due Date to Minimize Total Early Work and Late Work[J]. Journal of the Operations Research Society of China, 2026, 14(1): 129-148.

TrendMD

References

[1] Potts, C.N., Van Wassenhove, L.N.: Single machine scheduling to minimize total late work. Oper. Res. 40, 586-595(1992)
[2] Potts, C.N., Van Wassenhove, L.N.: Approximation algorithms for scheduling a single machine to minimize total late work. Oper. Res. Lett. 11, 261-266(1992)
[3] Mosheiov, G., Oron, D., Shabtay, D.: Minimizing total late work on a single machine with generalized due dates. Eur. J. Oper. Res. 293(3), 837-846(2021)
[4] Wu, C.C., Yin, Y., Wu, W.H., Chen, H.M., Cheng, S.R.: Using a branch-and-bound and a genetic algorithm for a single-machine total late work scheduling problem. Soft Comput. 20(4), 1329-1339(2016)
[5] Shabtay,D.,Mosheiov,G.,Oron,D.: Singlemachine schedulingwith common assignable due date/due window to minimize total weighted early and late work. Eur. J. Oper. Res. 303(1), 66-77(2022)
[6] Hariri, A.M.A., Potts, C.N., Van Wassenhove, L.N.: Single machine scheduling to minimize total weighted late work. ORSA J. Comput. 7(2), 232-242(1995)
[7] Li, P., Zhang, X.G., Wang, Q.: Single machine scheduling problem with minimize total weighted early work. J. Syst. Sci. Math. Sci. 4, 1068-1078(2021)
[8] Chen, X., Liang, Y., Sterna, M., Wang, W., Blazewicz, J.: Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date. Eur. J. Oper. Res. 284(1), 67-74(2020)
[9] Adamopoulos, G.I., Pappis, C.P.: Single machine scheduling with flow allowances. J. Oper. Res. Soc. 47, 1280-1285(1996)
[10] Jiang, Y.J., Zhang, Z., Song, X.L., Yin, Y.: Seru scheduling problems with multiple due-windows assignment and learning effect. J. Syst. Sci. Syst. Eng. 31, 480-511(2022)
[11] Na, Y.: Single machine due window assignment resource allocation scheduling with job-dependent learning effect. J. Appl. Math. Comput. 56(1), 715-725(2018)
[12] Feng, Q., Shang, W.P., Jiao, C.W.: Two-agent scheduling on a bounded parallel-batching machine with Makespan and maximum lateness objectives. J. Oper. Res. Soc. China 8, 189-196(2020)
[13] Chen, X., Shen, X., Kovalyov, M.Y., Sterna, M., Blazewicz, J.: Alternative algorithms for identical machines scheduling to maximize total early work with a common due date. Comput. Ind. Eng. 171, 108386(2022)
[14] Liu, W.W., Yao, Y., Jiang, C.: Single-machine resource allocation scheduling with due-date assignment, deterioration effect and position-dependent weights. Eng. Optim. 52(4), 701-714(2020)
[15] Pinedo, M.: Scheduling Theorem, Algorithms, and Systems, 5th edn. Springer, Berlin (2016)
[16] Chen, X., Xu, Y.F., Zheng, F., Liu, M.: Multitasking scheduling problems with a common due-window. RAIRO Oper. Res. 55, 1787-1798(2021)
[17] Bernhard, K., Jens, V.: Combinatorial Optimization, Theory and Algorithms, 6th edn. Springer, Berlin (2018)
[18] Woeginger, G. J.: When does a dynamic programming formulation guarantee the existence of an FPTAS?. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 17-19 January 1999, Baltimore, Maryland. ACM (1999)
[19] Jan-Erik, J., Sergey, K., Mikhail, Y., Kovalyov, E.P.: Single machine scheduling with assignable due dates to minimize maximum and total late work. Eur. J. Oper. Res. 308(1), 76-83(2023)
[20] Bazgan, C., Hugot, H., Vanderpooten, D.:Implementing an efficient FPTASfor the 0-1multi-objective knapsack problem. Eur. J. Oper. Res. 198(1), 47-56(2009)
[21] Chen, X., Shen, X., Kovalyov, M.Y., Sterna, M., Blazewicz, J.: Alternative algorithms for identical machines scheduling to maximize total early work with a common due date. Comput. Ind. Eng. 171, 108386(2022)