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
Journal of Scheduling

15-10-2023

Single-machine primary–secondary scheduling with total tardiness being the primary criterion

Authors: Qiulan Zhao, Jinjiang Yuan

Published in: Journal of Scheduling

Log in

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

search-config
loading …

Abstract

We study the single-machine primary–secondary scheduling problems in which the total tardiness is the primary criterion and the secondary criteria are the maximum lateness, the (weighted) number of tardy jobs, and the total weighted tardiness, respectively. These problems are known to be NP-hard, but their exact complexities (strongly NP-hard or pseudo-polynomially solvable) were posed by (in: Pardalos (ed) Complexity in numerical optimization, World Scientific, 1993) as open problems. In this paper, we show that these problems are solvable in pseudo-polynomial time.

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 "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
Appendix
Available only for authorised users
Literature
Agnetis, A., Billaut, J. C., Gawiejnowicz, S., Pacciarelli, D., & Soukhal, A. (2014). Multiagent scheduling: Models and algorithms. Springer.
Arkin, E. M., & Roundy, R. O. (1991). Weighted-tardiness scheduling on parallel machines with proportional weights. Operations Research, 39(1), 64–81.CrossRef
Chen, R. B., & Yuan, J. J. (2019). Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines. Journal of Scheduling, 22(5), 595–601.CrossRef
Della Croce, F., Tadei, R., Baracco, P., & Grosso, A. (1998). A new decomposition approach for the single machine total tardiness scheduling problem. Journal of the Operational Research Society, 49(10), 1101–1106.CrossRef
Du, J. Z., & Leung, J.Y.-T. (1990). Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research, 15(3), 483–495.CrossRef
Emmons, H. (1969). One-machine sequencing to minimize certain functions of job tardiness. Operations Research, 17(4), 701–715.CrossRef
Hoogeveen, H. (2005). Multicriteria scheduling. European Journal of Operational Research, 167(3), 592–623.CrossRef
Huo, Y. M., Leung, J.Y.-T., & Zhao, H. R. (2007). Complexity of two-dual criteria scheduling problems. Operations Research Letters, 35(2), 211–220.CrossRef
Koulamas, C., & Kyparisis, G. J. (2001). Single machine scheduling with release times, deadlines and tardiness objectives. European Journal of Operational Research, 133(2), 447–453.CrossRef
Lawler, E. L. (1977). A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics, 1(1), 331–342.CrossRef
Lawler, E. L., & Moore, J. M. (1969). A functional equation and its applications to resource allocation and sequencing problems. Management Science, 16(1), 77–84.CrossRef
Lee, C. Y., & Vairaktarakis, G. (1993). Complexity of single machine hierarchical scheduling: A survey. In P. M. Pardalos (Ed.), Complexity in numerical optimization (pp. 269–298). World Scientific.
Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1(1), 343–362.CrossRef
Sahni, S. (1976). Algorithms for scheduling independent tasks. Journal of the Association of Computing Machinery, 23(1), 116–127.
Smith, W. E. (1956). Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3(1), 59–66.CrossRef
T’kindt, V. & Billaut, J. C. (2006). Multicriteria scheduling: Theory, models and algorithms (2nd ed.). Springer.
Yuan, J. J. (2017). Unary NP-hardness of minimizing the number of tardy jobs with deadlines. Journal of Scheduling, 20(2), 211–218.CrossRef
Metadata
Title
Single-machine primary–secondary scheduling with total tardiness being the primary criterion
Authors
Qiulan Zhao
Jinjiang Yuan
Publication date
15-10-2023
Publisher
Springer US
Published in
Journal of Scheduling
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI
https://doi.org/10.1007/s10951-023-00793-7