A heuristic for single machine common due date assignment problem with different earliness/tardiness weights
Tóm tắt
This paper considers the common due date assignment for single machine weighted earliness/tardiness scheduling problem with different earliness and tardiness weights for jobs where the objective is to minimize the cost of the sum of weighted earliness/tardiness and assignment common due date. The single machine common due date assignment problem where all jobs have the same earliness/tardiness weight has a polynomial-time algorithm to solve it optimally. Furthermore, some properties for the problem where the common due date is an input have been revealed by researchers in the literature. This paper proposes a heuristic algorithm for the problem using the revealed properties of similar problems’ optimal solutions such as the V-shaped property and zero-start time of the machine. The experimental study of this paper shows that the proposed heuristic finds better solutions for the problems in a reasonable time than a commercial solver has when the problem size is increased.
Tài liệu tham khảo
Arık, O.A., Schutten, M., Topan, E.: Weighted earliness/tardiness parallel machine scheduling problem with a common due date. Expert Syst. Appl. 187, 115916 (2022). https://doi.org/10.1016/J.ESWA.2021.115916
Panwalkar, S.S., Smith, M.L., Seidmann, A.: Common due date assignment to minimize total penalty for the one machine scheduling problem. Oper. Res. 30, 391–399 (1982). https://doi.org/10.1287/opre.30.2.391
Hall, N.G., Posner, M.E.: Earliness-tardiness scheduling problems, I: weighted deviation of completion times about a common due date. Oper. Res. 39, 836–846 (1991). https://doi.org/10.1287/opre.39.5.836
Kanet, J.J.: Minimizing the average deviation of job completion times about a common, due date. Nav. Res. Logist. Q. 28, 643–651 (1981). https://doi.org/10.1002/nav.3800280411
Raghavachari, M., Zammouri, M.: Single machine scheduling with coefficient of variation minimization. Eur. J. Oper. Res. 62, 302–310 (1992). https://doi.org/10.1016/0377-2217(92)90120-X
Bector, C.R., Gupta, Y.P., Gupta, M.C.: V-shape property of optimal sequence of jobs about a common due date on a single machine. Comput. Oper. Res. 16, 583–588 (1989). https://doi.org/10.1016/0305-0548(89)90043-9
Raghavachari, M.: A V-shape property of optimal schedule of jobs about a common due date. Eur. J. Oper. Res. 23, 401–402 (1986). https://doi.org/10.1016/0377-2217(86)90306-1
Arık, O.A.: Single machine earliness/tardiness scheduling problem with grey processing times and the grey common due date. Grey Syst. Theory Appl. 11, 95–109 (2021). https://doi.org/10.1108/gs-01-2020-0010
Cheng, T.C.E., Gupta, M.C.: Survey of scheduling research involving due date determination decisions. Eur. J. Oper. Res. 38, 156–166 (1989). https://doi.org/10.1016/0377-2217(89)90100-8
Elion, S.: Production scheduling. In: Haley, K.B. (ed.) Operations Research ’78, pp. 237–266. North-Holland Publishing Company, Amsterdam (1979)
Gordon, V., Proth, J.-M., Chu, C.: A survey of the state-of-the-art of common due date assignment and scheduling research. Eur. J. Oper. Res. 139, 1–25 (2002). https://doi.org/10.1016/S0377-2217(01)00181-3
Seidmann, A., Panwalkar, S.S., Smith, M.L.: Optimal assignment of due-dates for a single processor scheduling problem. Int. J. Prod. Res. 19, 393–399 (1981). https://doi.org/10.1080/00207548108956667
Cheng, T.C.E.: An alternative proof of optimality for the common due-date assignment problem. Eur. J. Oper. Res. 37, 250–253 (1988). https://doi.org/10.1016/0377-2217(88)90334-7
Sung, C.S., Min, J.I., Park, C.K.: Heuristic algorithms for a single-machine common due date assignment under earliness/tardiness measure. J. Oper. Res. Soc. Jpn. 36, 121–133 (1993)
Koulamas, C.: Common due date assignment with generalized earliness/tardiness penalties. Comput. Ind. Eng. 109, 79–83 (2017). https://doi.org/10.1016/j.cie.2017.04.040
De, P., Ghosh, J.B., Wells, C.E.: Optimal delivery time quotation and order sequencing. Decis. Sci. 22, 379–390 (1991). https://doi.org/10.1111/J.1540-5915.1991.TB00353.X
Koulamas, C.: A unified solution approach for the due date assignment problem with tardy jobs. Int. J. Prod. Econ. 132, 292–295 (2011). https://doi.org/10.1016/J.IJPE.2011.04.023
Kahlbacher, H.G., Cheng, T.C.E.: Parallel machine scheduling to minimize costs for earliness and number of tardy jobs. Discrete Appl. Math. 47, 139–164 (1993). https://doi.org/10.1016/0166-218X(93)90088-6
Li, S.-S., Chen, R.-X.: Scheduling with common due date assignment to minimize generalized weighted earliness–tardiness penalties. Optim. Lett. 14, 1681–1699 (2020). https://doi.org/10.1007/s11590-019-01462-5
Shabtay, D., Mosheiov, G., Oron, D.: Single machine scheduling with common assignable due date/due window to minimize total weighted early and late work. Eur. J. Oper. Res. (2022). https://doi.org/10.1016/J.EJOR.2022.02.017
Yeung, W.K., Oguz, C., Cheng, T.C.E.: Single-machine scheduling with a common due window. Comput. Oper. Res. 28, 157–175 (2001). https://doi.org/10.1016/S0305-0548(99)00097-0
De, P., Ghosh, J.B., Wells, C.E.: Due-date assignmentand early/tardy scheduling on identical parallel machines. Nav. Res. Logist. 41, 17–32 (1994). https://doi.org/10.1002/1520-6750(199402)41:1<17::AID-NAV3220410103>3.0.CO;2-X
Cheng, T.C., Chen, Z.-L.: Parallel-machine scheduling problems with earliness and tardiness penalties. J. Oper. Res. Soc. 45, 685–695 (1994). https://doi.org/10.1057/jors.1994.106
Diamond, J.E., Cheng, T.C.E.: Error bound for common due date assignment and job scheduling on parallel machines. IIE Trans. Insti. Ind. Eng. 32, 445–448 (2000). https://doi.org/10.1023/A:1007644826949
Mosheiov, G.: A common due-date assignment problem on parallel identical machines. Comput. Oper. Res. 28, 719–732 (2001). https://doi.org/10.1016/S0305-0548(99)00127-6
Xiao, W.-Q., Li, C.-L.: Approximation algorithms for common due date assignment and job scheduling on parallel machines. IIE Trans. Inst. Ind. Eng. 34, 466–477 (2002). https://doi.org/10.1080/07408170208928883
Mosheiov, G., Yovel, U.: Minimizing weighted earliness-tardiness and due-date cost with unit processing-time jobs. Eur. J. Oper. Res. 172, 528–544 (2006). https://doi.org/10.1016/j.ejor.2004.10.021
Min, L., Cheng, W.: Genetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness/tardiness scheduling problems. Robot Comput. Integr. Manuf. 22, 279–287 (2006). https://doi.org/10.1016/j.rcim.2004.12.005
Drobouchevitch, I.G., Sidney, J.B.: Minimization of earliness, tardiness and due date penalties on uniform parallel machines with identical jobs. Comput. Oper. Res. 39, 1919–1926 (2012). https://doi.org/10.1016/j.cor.2011.05.012
Kim, J.-G., Kim, J.-S., Lee, D.-H.: Fast and meta-heuristics for common due-date assignment and scheduling on parallel machines. Int. J. Prod. Res. 50, 6040–6057 (2012). https://doi.org/10.1080/00207543.2011.644591
Xiong, X., Wang, D., Cheng, E., Wu, T.C., Yin, C.-C.: Single-machine scheduling and common due date assignment with potential machine disruption. Int. J. Prod. Res. 56, 1345–1360 (2018). https://doi.org/10.1080/00207543.2017.1346317
Ng Daniel, C.T.D., Cheng, T.C.E., Kovalyov, M.Y., Lam, S.S.: Single machine scheduling with a variable common due date and resource-dependent processing times. Comput. Oper. Res. 30, 1173–1185 (2003). https://doi.org/10.1016/S0305-0548(02)00066-7
Keha, A.B., Khowala, K., Fowler, J.W.: Mixed integer programming formulations for single machine scheduling problems. Comput. Ind. Eng. 56, 357–367 (2009). https://doi.org/10.1016/J.CIE.2008.06.008
Biskup, D., Feldmann, M.: Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates. Comput. Oper. Res. 28, 787–801 (2001). https://doi.org/10.1016/S0305-0548(00)00008-3