Abstract
We solve a single machine problem of constructing a schedule of tasks with arbitrary due dates on a single machine that minimizes the total earliness/tardiness in relation to their due dates. This problem is solved in three different formulations: (1) the start time of the machine is fixed. In this case the problem is NP-hard; (2) the start time of the machine belongs to a specified time segment. The problem is intractable because there is no exact polynomial algorithm for its solving; (3) the start time of the machine is arbitrary. The problem is intractable because there is no exact polynomial algorithm for its solving. For the first two problems we give PSC-algorithms, each of them contains sufficient signs of a feasible solution optimality and is based on the optimal solution for the single machine problem to minimize the total tardiness of tasks in relation to their various due dates (with equal weights). We show that the PSC-algorithm of its solving is a simplified modification of the PSC-algorithm presented in Chap. 4. For the third problem solving we build an efficient approximation algorithm.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsNotes
- 1.
All schedules obtained during the considered problem solving are feasible including those with tardy tasks.
References
Zgurovsky, M.Z., Pavlov, A.A.: Prinyatie Resheniy v Setevyh Sistemah s Ogranichennymi Resursami (Пpинятиe peшeний в ceтeвыx cиcтeмax c oгpaничeнными pecypcaми; Decision Making in Network Systems with Limited Resources). Naukova dumka, Kyiv (2010) (in Russian)
Pavlov, A.A., Misura, E.B.: PDS-algoritm minimizacii summarnogo operejeniya i zapazdyvaniya pri vypolnenii rabot odnim priborom, esli moment zapuska pribora fiksirovannyi (ПДC-aлгopитм минимизaции cyммapнoгo oпepeжeния и зaпaздывaния пpи выпoлнeнии paбoт oдним пpибopoм, ecли мoмeнт зaпycкa пpибopa фикcиpoвaнный; PDC-algorithm for total earliness and tardiness minimization on single machine for the case if the machine start time is fixed). Paper Presented at the 21st International Conference on Automatic Control Automatics-2014, National Technical University of Ukraine, Kyiv, 23–27 Sept 2014 (in Russian)
Pavlov, A.A., Misura, E.B.: PDS-algoritmy resheniya zadach sostavleniya raspisaniy po kriteriyu operejeniya/zapazdyvaniya na odnom pribore (ПДC-aлгopитмы peшeния зaдaч cocтaвлeния pacпиcaний пo кpитepию oпepeжeния/зaпaздывaния нa oднoм пpибope; PDC-algorithms to solve single machine earliness/tardiness scheduling problems). Visnyk NTUU KPI Inform. Oper. Comput. Sci. 60, 4–19 (2014) (in Russian)
Pavlov, A.A., Misura, E.B., Kostik, D.Y.: Minimizaciya summarnogo zapazdyvaniya pri nalichii zadanii s otricatel’nymi znacheniyami direktivnyh srokov (Mинимизaция cyммapнoгo зaпaздывaния пpи нaличии зaдaний c oтpицaтeльными знaчeниями диpeктивныx cpoкoв; Minimizing total tasks tardiness in the presence of negative deadline values). Visnyk NTUU KPI Inform. Oper. Comput. Sci. 53, 3–5 (2011) (in Russian)
Pavlov, A.A., Misura, E.B., Khalus, E.A.: Skladannya rozkladu vikonannya zavdan’ na odnomu priladi z metoyu minimizacii sumarnogo vyperedjennya ta znahodjennya maksimal’nogo pizn’ogo momentu pochatku vikonannya zavdan’ v dopustimomu rozkladi (Cклaдaння poзклaдy викoнaння зaвдaнь нa oднoмy пpилaдi з мeтoю мiнiмiзaцiї cyмapнoгo випepeджeння тa знaxoджeння мaкcимaльнoгo пiзньoгo мoмeнтy пoчaткy викoнaння зaвдaнь в дoпycтимoмy poзклaдi; Single machine scheduling to minimize the total earliness and find the latest start time of tasks in a feasible schedule). Paper Presented at the 21st International Conference on Automatic Control Automatics-2014, National Technical University of Ukraine, Kyiv, 23–27 Sept 2014 (in Ukrainian)
Feldmann, M., Biskup, D.: Single-machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic approaches. Comput. Ind. Eng. 44(2), 307–323 (2003). https://doi.org/10.1016/s0360-8352(02)00181-x
Valente, J.M.S., Alves, R.A.F.S.: Improved heuristics for the early/tardy scheduling problem with no idle time. Comput. Oper. Res. 32(3), 557–569 (2005). https://doi.org/10.1016/j.cor.2003.08.003
Wodecki, M.: A block approach to earliness-tardiness scheduling problems. Int. J. Adv. Manuf. Technol. 40(7–8), 797–807 (2008). https://doi.org/10.1007/s00170-008-1395-7
Kanet, J.J.: Minimizing the average deviation of job completion times about a common due date. Naval Res. Logistics Q. 28(4), 643–651 (1981). https://doi.org/10.1002/nav.3800280411
Lawler, E.L.: A fully polynomial approximation scheme for the total tardiness problem. Oper. Res. Lett. 1(6), 207–208 (1982). https://doi.org/10.1016/0167-6377(82)90022-0
T’kindt, V., Billaut, J.-C.: Multicriteria Scheduling: Theory, Models and Algorithms. Springer, Berlin (2002). https://doi.org/10.1007/978-3-662-04986-0
Baker, K.R., Scudder, G.D.: Sequencing with earliness and tardiness penalties: a review. Oper. Res. 38(1), 22–36 (1990). https://doi.org/10.1287/opre.38.1.22
Jin, S., Mason, S.J.: Minimizing earliness and tardiness costs on a single machine with uncommon job due dates. Preprint. Bell Engineering Center, University of Arkansas, Fayetteville (2004)
Mason, S.J., Jin, S., Jampani, J.: A moving block heuristic for minimizing earliness and tardiness. J. Manuf. Syst. 24(4), 328–338 (2005). https://doi.org/10.1016/s0278-6125(05)80017-2
Garey, M.R., Tarjan, R.E., Wilfong, G.T.: One-processor scheduling with symmetric earliness and tardiness penalties. Math. Oper. Res. 13(2), 330–348 (1988). https://doi.org/10.1287/moor.13.2.330
Yano, C.A., Kim, Y.-D.: Algorithms for a class of single-machine weighted tardiness and earliness problems. Eur. J. Oper. Res. 52(2), 167–178 (1991). https://doi.org/10.1016/0377-2217(91)90078-a
Davis, J.S., Kanet, J.J.: Single-machine scheduling with early and tardy completion costs. Naval Res. Logistics 40(1), 85–101 (1993). https://doi.org/10.1002/1520-6750(199302)40:1<85:aid-nav3220400106>3.0.co;2-c
Ow, P.S., Morton, T.E.: The single machine early/tardy problem. Manag. Sci. 35(2), 177–191 (1989). https://doi.org/10.1287/mnsc.35.2.177
Szwarc, W., Mukhopadhyay, S.K.: Optimal timing scheduling in earliness-tardiness single machine sequencing. Naval Res. Logistics 42(7), 1109–1114 (1995). https://doi.org/10.1002/1520-6750(199510)42:7<1109:aid-nav3220420709>3.0.co;2-5
Sridharan, V., Zhou, Z.: A decision theory based scheduling procedure for single-machine weighted earliness and tardiness problem. Eur. J. Oper. Res. 94(2), 292–301 (1996). https://doi.org/10.1016/0377-2217(96)00133-6
Wan, G., Yen, B.P.C.: Tabu search for single-machine scheduling with distinct due windows and weighted earliness/tardiness penalties. Eur. J. Oper. Res. 142(2), 271–281 (2002). https://doi.org/10.1016/s0377-2217(01)00302-2
Szwarc, W.: Adjacent orderings in single-machine scheduling with earliness and tardiness penalties. Naval Res. Logistics 40(2), 229–243 (1993). https://doi.org/10.1002/1520-6750(199303)40:2<229:aid-nav3220400207>3.0.co;2-r
Lee, C.Y., Choi, J.Y.: A generic algorithm for job sequencing problem with distinct due dates and general early-tardy penalty weights. Comput. Oper. Res. 22(8), 857–869 (1995). https://doi.org/10.1016/0305-0548(94)00073-h
Bank, J., Werner, F.: Heuristic algorithm for unrelated parallel machine scheduling with a common due date, release dates, and linear earliness and tardiness penalties. Math. Comput. Model. 33(4–5), 363–383 (2001). https://doi.org/10.1016/s0895-7177(00)00250-8
Gordon, V., Proth, J.-M., Chu, C.: A survey of the state-of-art of common due date assignment and scheduling research. Eur. J. Oper. Res. 139(1), 1–25 (2002). https://doi.org/10.1016/s0377-2217(01)00181-3
Valente, J.M.S., Alves, R.A.F.S.: Filtered and recovering beam search algorithms for the early/tardy scheduling problem with no idle time. Comput. Ind. Eng. 48(2), 363–375 (2005). https://doi.org/10.1016/j.cie.2005.01.020
Tsai, T.-I.: A genetic algorithm for solving the single machine earliness/tardiness problem with distinct due dates and ready times. Int. J. Adv. Manuf. Technol. 31(9–10), 994–1000 (2007). https://doi.org/10.1007/s00170-005-0261-0
Hoogeveen, J.A., Van de Velde, S.L.: A branch-and-bound algorithm for single-machine earliness–tardiness scheduling with idle time. INFORMS J. Comput. 8(4), 402–412 (1996). https://doi.org/10.1287/ijoc.8.4.402
Tanaka, S., Fujikuma, S., Araki, M.: An exact algorithm for single-machine scheduling without machine idle time. J. Sched. 12(6), 575–593 (2009). https://doi.org/10.1007/s10951-008-0093-5
Du, J., Leung, J.Y.-T.: Minimizing total tardiness on one processor is NP-hard. Math. Oper. Res. 15(3), 483–495 (1990). https://doi.org/10.1287/moor.15.3.483
Tanaev, V.S., Shkurba, V.V.: Vvedenie v Teoriju Raspisaniy (Bвeдeниe в тeopию pacпиcaний; Introduction to Scheduling Theory). Nauka, Moscow (1975) (in Russian)
Lawler, E.L.: A “pseudopolynomial” algorithm for sequencing jobs to minimize total tardiness. Ann. Discr. Math. 1, 331–342 (1977). https://doi.org/10.1016/S0167-5060(08)70742-8
Potts, C.N., Van Wassenhove, L.N.: A decomposition algorithm for the single machine total tardiness problem. Oper. Res. Lett. 1, 177–181 (1982). https://doi.org/10.1016/0167-6377(82)90035-9
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Zgurovsky, M.Z., Pavlov, A.A. (2019). The Total Earliness/Tardiness Minimization on a Single Machine with Arbitrary Due Dates. In: Combinatorial Optimization Problems in Planning and Decision Making. Studies in Systems, Decision and Control, vol 173. Springer, Cham. https://doi.org/10.1007/978-3-319-98977-8_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-98977-8_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-98976-1
Online ISBN: 978-3-319-98977-8
eBook Packages: EngineeringEngineering (R0)