Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Scheduling to Maximize the Number of Just-in-Time Jobs: A Survey Read chapter Read first chapter

2012 | OriginalPaper | Chapter

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

Authors : Ameur Soukhal, Nguyen Huynh Toung

Published in: Just-in-Time Systems

Publisher: Springer New York

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Mixed-Integer Programming Models for Flowshop Scheduling Problems Minimizing the Total Earliness and Tardiness
next chapter No-Wait Scheduling Problems with Batching Machines
Literature
1.
2.
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
3.
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
4.
5.
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)
6.
Bruno, J., Coffman, Jr.E.G., Sethi, R.: Scheduling independent tasks to reduce mean finishing time. Communicaiton of the ACM 17, 382–387 (1974)
7.
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
8.
9.
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.
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.
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.
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.
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.
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
Metadata
Title
Just-in-Time Scheduling with Equal-Size Jobs
Authors
Ameur Soukhal
Nguyen Huynh Toung
Copyright Year
2012
Publisher
Springer New York
Book
Just-in-Time Systems

Print ISBN: 978-1-4614-1122-2

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

Copyright Year: 2012

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