nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

5. The Total Earliness/Tardiness Minimization on a Single Machine with Arbitrary Due Dates

verfasst von : Michael Z. Zgurovsky, Alexander A. Pavlov

Erschienen in: Combinatorial Optimization Problems in Planning and Decision Making

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel The Total Weighted Tardiness of Tasks Minimization on a Single Machine

Nächstes Kapitel The Total Tardiness of Tasks Minimization on Identical Parallel Machines with Arbitrary Fixed Times of Their Start and a Common Due Date

All schedules obtained during the considered problem solving are feasible including those with tardy tasks.

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-xCrossRef

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.003CrossRefMATH

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-7CrossRef

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.3800280411CrossRefMATH

10.

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-0CrossRefMATH

11.

T’kindt, V., Billaut, J.-C.: Multicriteria Scheduling: Theory, Models and Algorithms. Springer, Berlin (2002). https://doi.org/10.1007/978-3-662-04986-0CrossRef

12.

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.22MathSciNetCrossRefMATH

13.

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)

14.

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-2CrossRef

15.

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.330MathSciNetCrossRefMATH

16.

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-aCrossRefMATH

17.

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-cCrossRefMATH

18.

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.177MathSciNetCrossRefMATH

19.

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-5CrossRefMATH

20.

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-6CrossRefMATH

21.

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-2MathSciNetCrossRefMATH

22.

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-rMathSciNetCrossRefMATH

23.

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-hCrossRefMATH

24.

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-8MathSciNetCrossRefMATH

25.

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-3MathSciNetCrossRefMATH

26.

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.020CrossRef

27.

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-0CrossRef

28.

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.402CrossRefMATH

29.

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-5MathSciNetCrossRefMATH

30.

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.483MathSciNetCrossRefMATH

31.

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)

32.

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-8MathSciNetCrossRefMATH

33.

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-9CrossRefMATH

Titel: The Total Earliness/Tardiness Minimization on a Single Machine with Arbitrary Due Dates
verfasst von: Michael Z. Zgurovsky
Alexander A. Pavlov
Verlag: Springer International Publishing
Buch: Combinatorial Optimization Problems in Planning and Decision Making
Print ISBN: 978-3-319-98976-1

Electronic ISBN: 978-3-319-98977-8

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-319-98977-8_5

Premium Partner

Marktübersichten

Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen.

Zur Marktübersicht

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner

Marktübersichten