nach oben

Erschienen in:

2012 | OriginalPaper | Buchkapitel

6. Just-in-Time Scheduling with Equal-Size Jobs

verfasst von : Ameur Soukhal, Nguyen Huynh Toung

Erschienen in: Just-in-Time Systems

Verlag: Springer New York

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This chapter deals with common due date scheduling problem on single and parallel machines in which job processing times are identical. The objective is to minimize the total weighted earliness–tardiness. According to the common due date, two cases are considered. In the first case, the due date is given which involves that the common due date is enough early (restrictive version) or not (non-restrictive version) to constraint the optimal solution. In this case, there is no cost related to its value. The second case deals with unknown due date which is a decision variables. It means that the decision maker not only takes sequencing and scheduling decisions to minimize the total weighted earliness–tardiness but also determines the optimal value of due date which is specified as controllable parameter.

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 Mixed-Integer Programming Models for Flowshop Scheduling Problems Minimizing the Total Earliness and Tardiness

Nächstes Kapitel No-Wait Scheduling Problems with Batching Machines

Ahuja, R.K., Orlin, J.B.: A fast and simple algorithm for the maximum flow problem. Operations Research 37, 748–759 (1989)MathSciNetMATHCrossRef

Alidaee, B., Panwalkar, S.S.: Single stage minimum absolute lateness problem with a common due date on non-identical machines. Journal of the Operational Research Society 44(1), 29–36 (1993)MATH

Bagchi, U., Sullivan, R.S., Chang, Y.L.: Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties about a common due-date. Naval Research Logistics 34(5), 739–751 (1987)MathSciNetMATHCrossRef

Baker, K.R., Scudder, G.D.: Sequencing with earliness and tardiness penalties: a review. Operations Research 38, 22–36 (1990)MathSciNetMATHCrossRef

Baptiste, P., Brucker, P.: Scheduling equal processing time jobs. In JY Leung (Ed.): Handbook of scheduling: algorithms, models and performance analysis, CRC Press, Boca Raton, FL, USA (2004)

Bruno, J., Coffman, Jr.E.G., Sethi, R.: Scheduling independent tasks to reduce mean finishing time. Communicaiton of the ACM 17, 382–387 (1974)

Cheng, T.C.E., Chen, Z.L.: Parallel-machine scheduling problems with earliness and tardiness penalties. Journal of the Operational Research Society 45, 685–695 (1994)MATH

Cole, R., Ost, K., Schirra, S.: Edge-coloring bipartite multigraphs in O(ElogD) time. Combinatorica 21, 5–12 (2001)MathSciNetMATHCrossRef

De, P., Ghosh, J.B., Wells, C.E.: Due-date assignment and early/tardy scheduling on identical parallel machines. Naval Research Logistics 41(1), 17–32 (1994)MathSciNetMATHCrossRef

10.

Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the Association for Computing Machinery 19, 248–264 (1972)MATHCrossRef

11.

Emmons, H: Scheduling to a common due-date on parallel uniform processors. Naval Research Logistics Quarterly 34, 803–810 (1987)MathSciNetMATHCrossRef

12.

Garey, M.R., Tarjan, R.E., Wilfong, G.T.: One-processor scheduling with assymmetric earliness and tardiness penalties. Mathematics of Operations Research 13, 330–348 (1988)MathSciNetMATHCrossRef

13.

Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum-flow problem. Journal of the Association for Computing Machinery 35, 921–940 (1988)MathSciNetMATHCrossRef

14.

Gordon, V., Proth, J.M., Chu, C.: A survey of the state-of-art of common due date assignment and scheduling research. European Journal of Operational Research 139, 1–25 (2002)MathSciNetMATHCrossRef

15.

Gordon, V. S., Proth, J.-M., Strusevich, V. A.: Scheduling with due date assignment. In Handbook of scheduling, J.Y.T Leung eds., CRC Press, Boca Raton, FL, USA (2004)

16.

Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics 5, 287–326 (1979)

17.

Hall, N.G., Kubiak, W., Sethi, S.P.: Earliness-tardiness scheduling problem, II: Deviation of completion times about a restrictive common due date. Operations Research 39, 847–856 (1991)MathSciNetMATH

18.

Hall, N.G., Posner, M.E.: Earliness-tardiness scheduling problem, I: Weighted deviation of completion times about a common due date. Operations Research 39,836–846 (1991)MathSciNetMATH

19.

Hoogeveen, J.A., Van de Velde, S.L.: Scheduling around a small common due date. European Journal of Operational Research 55(2), 237–242 (1991)MATHCrossRef

20.

Hoogeveen, J.A., Oosterhout, H., Van de Velde, S.L.: New lower and upper bounds for scheduling around a small common due date. Operations research 42(1), 102–110 (1994)MATHCrossRef

21.

Hopcroft, J.E., Karp, R.M.: An n ^5 ∕ 2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing 2, 225–231 (1973)MathSciNetMATHCrossRef

22.

Huynh Tuong, N., Soukhal, A.: Due dates assignment and JIT scheduling with equal-size jobs. European Journal of Operational Research 205(2), 280-289 (2010)MathSciNetMATHCrossRef

23.

Huynh Tuong, N., Soukhal, A.: Some new polynomial cases in just-in-time scheduling problems with multiple due dates. In Proceeding of the 6th International Conference on Research, Innovation & Vision for the Future in Computing & Communications Technologies (RIVF’08), Ho Chi Minh (Vietnam), 36–41 (2008)

24.

Huynh Tuong, N., Soukhal, A.: Ordonnancement juste-à-temps sur une seule machine avec date de fin souhaitée commune. 9ème Congrés de la Société Française de Recherche Opérationnelle et d’Aide à la Décision (ROADEF’08), Febuary 25–27, Clermont-Ferrand (France), 146–148 (2008)

25.

Huynh Tuong, N., Soukhal, A.: Polynomial cases and PTAS for just-in-time scheduling on parallel machines around a common due date. 11th International Workshop on Project Management and Scheduling (PMS’08), April 28-30, Istanbul (Turkey), 152–155 (2008)

26.

Józefowska, J.: Just-in-time Scheduling : Models and Algorithms for Computer and Manufacturing Systems. Springer-Verlag New York Inc. (2007)

27.

Jurisch, B., Kubiak, W., Józefowska, J.: Algorithms for minclique scheduling problems. Discrete Applied Mathematics 72, 115–139 (1997)MathSciNetMATHCrossRef

28.

Kaminsky, P., Hochbaum, D.: Due date quotation models and algorithms. In Handbook of scheduling, J.Y.T Leung eds., CRC Press, Boca Raton, FL, USA (2004)

29.

Kanet, J.J.: Minimizing the average deviation of job completion times about a common due date. Naval Research Logistics Quarterly 28, 643–651 (1981)MATHCrossRef

30.

Kao, M.-Y., Lam, T.-W., Sung, W.-K., Ting, H.-F.: A decomposition theorem for maximum weight bipartite matchings. SIAM Journal on Computing 31, 18–26 (2002)MathSciNetCrossRef

31.

Kovalyov, M.Y.: Soft and negotiable release and due dates in supply chain scheduling. Rapport de projet ORDO-COO-OC de GDR RO (2006)

32.

Kovalyov, M.Y., Kubiak, W.: A fully polynomial approximation scheme for the weighted earliness-tardiness problem. Operations Research 47, 757–761 (1999)MathSciNetMATHCrossRef

33.

Kubiak, W., Lou, S., Sethi, S.: Equivalence of mean flow time problems and mean absolute deviation problems. Operations Research Letters 9, 371–374 (1990)MATHCrossRef

34.

Kuhn, W.H.: The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly 2, 83–97 (1955)MathSciNetCrossRef

35.

Mosheiov, G., Yovel, U.: Minimizing weighted earliness–tardiness and due date cost with unit processing–time jobs. European Journal of Operations Research 172, 528–544 (2006)MathSciNetMATHCrossRef

36.

Mosheiov, G., Sarig, A.: Due-date assignment on uniform machines. European Journal of Operational Research 193(1), 49–58 (2009)MathSciNetMATHCrossRef

37.

Panwalkar, S.S., Smith, M.L., Seidmann, A.: Common due-date assignment to minimize total penalty for the one machine scheduling problem. Operations Research 30, 391–399 (1982)MATHCrossRef

38.

Smith, W.E.: Various optimizers for single-stage production. Naval Research Logistics Quarterly 3, 59–66 (1956)MathSciNetCrossRef

39.

Sourd, F.: New exact algorithms for one-machine earliness-tardiness scheduling. INFORMS Journal of Computing 21(1), 167–175 (2009)MathSciNetMATHCrossRef

40.

Sun, H., Wang, G.: Parallel machine earliness and tardiness scheduling with proportional weights. Computers & Operations Research 30(5), 801–808 (2003)MATHCrossRef

41.

T’kindt, V., Billaut, J.-C.: Multicriteria Scheduling: Theory, Models and Algorithms. Springer, Heidelberg (2006)MATH

42.

Webster, S.: The complexity of scheduling job families about a common due date. Operations Research Letters 20(2), 65–74 (1997)MathSciNetMATHCrossRef

43.

Xiao, W.-Q., Li, C.-L.: Approximation algorithms for common due date assignment and job scheduling on parallel machines. IIE Transactions 34(5), 467–477 (2002)MathSciNetCrossRef

44.

Yuan, J.: The NP-hardness of the single machine common due date weighted tardiness problem. Systems Science and Mathematical Sciences 5, 328–333 (1992)MathSciNetMATH

Titel: Just-in-Time Scheduling with Equal-Size Jobs
verfasst von: Ameur Soukhal
Nguyen Huynh Toung
Verlag: Springer New York
Buch: Just-in-Time Systems
Print ISBN: 978-1-4614-1122-2

Electronic ISBN: 978-1-4614-1123-9

Copyright-Jahr: 2012
DOI: https://doi.org/10.1007/978-1-4614-1123-9_6

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"