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
Published in: Journal of Scheduling 4/2023

25-01-2023

A note: maximizing the weighted number of Just-in-Time jobs for a given job sequence

Authors: Enrique Gerstl, Gur Mosheiov

Published in: Journal of Scheduling | Issue 4/2023

Log in

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

search-config
loading …

Abstract

We study a single machine scheduling problem to maximize the weighted number of Just-in-Time jobs, i.e., jobs which are completed exactly at their due-dates. We focus on the case that the job sequence is given. A pseudo-polynomial solution algorithm has been published for this problem, and we introduce here an efficient polynomial time dynamic programming algorithm. The new algorithm is tested numerically, and the results are compared to those obtained by the old algorithm. While the running times required by both algorithms for solving large instances are extremely small, it appears that the new algorithm performs better in two aspects: (1) The resulting running time is independent of the actual density of the due-dates, (2) The required memory is significantly reduced. An extension to a two-machine flowshop is provided, and this case is shown to remain polynomially solvable.
previous article A note on the shifting bottleneck procedure for job shop scheduling

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
Chen, R. X., Li, S. S., & Li, W. J. (2019). Multi-agent scheduling in a no-wait flow shop system to maximize the weighted number of just-in-time jobs. Engineering Optimization, 51(2), 217–230.CrossRef
Choi, B. C., & Yoon, S. H. (2007). Maximizing the weighted number of just-in-time jobs in flow shop scheduling. Journal of Scheduling, 10(4), 237–243.CrossRef
Elalouf, A., Levner, E., & Tang, H. (2013). An improved FPTAS for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem. Journal of Scheduling, 16(4), 429–435.CrossRef
Fry, T., Armstrong, R. D., & Rosen, L. D. (1990). Single machine scheduling to minimize mean absolute lateness: A heuristic solution. Computers & Operations Research, 17, 105–112.CrossRef
Fry, T. D., Armstrong, R. D., & Blackstone, J. H. (1987). Minimizing weighted absolute deviation in single machine scheduling. IIE Transactions, 19, 445–450.CrossRef
Gerstl, E., Mor, B., & Mosheiov, G. (2015). A note: Maximizing the weighted number of just-in-time jobs on a proportionate flowshop. Information Processing Letters, 115, 159–162.CrossRef
Gerstl, E., & Mosheiov, G. (2020). Single machine scheduling to maximize the number of on-time jobs with generalized due-dates. Journal of Scheduling, 23(3), 289–299.CrossRef
Gilenson, M., & Shabtay, D. (2019). Multi-scenario scheduling to maximise the weighted number of just-in-time jobs. Journal of the Operational Research Society, 72, 1–18.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326.CrossRef
Hiraishi, K., Levner, E., & Vlach, M. (2002). Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs. Computers & Operations Research, 29(7), 841–848.CrossRef
Jolai, F., Amalnick, M. S., Alinaghian, M., Shakhsi-Niaei, M., & Omrani, H. (2011). A hybrid memetic algorithm for maximizing the weighted number of just-in-time jobs on unrelated parallel machines. Journal of Intelligent Manufacturing, 22(2), 247–261.CrossRef
Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of computer computations (pp. 85–103). Boston, MA: Springer.
Lann, A., & Mosheiov, G. (1996). Single machine scheduling to minimize the number of early/tardy jobs. Computers and Operations Research, 23, 769–781.CrossRef
Liaw, C. F., Cheng, C. Y., & Chen, M. (2002). The total completion time open shop scheduling problem with a given sequence of jobs on one machine. Computers & Operations Research, 29, 1251–1266.CrossRef
Mosheiov, G., & Shabtay, D. (2013). Maximizing the weighted number of just-in-time jobs on a single machine with position-dependent processing times. Journal of Scheduling, 16, 519–527.CrossRef
Shabtay, D. (2012). The just-in-time scheduling problem in a flow-shop scheduling system. European Journal of Operational Research, 216, 521–532.CrossRef
Shabtay, D., & Bensoussan, Y. (2012). Maximizing the weighted number of just-in-time jobs in several two-machine scheduling systems. Journal of Scheduling, 15(1), 39–47.CrossRef
Shabtay, D., Bensoussan, Y., & Kaspi, M. (2012). A bicriteria approach to maximize the weighted number of just-in-time jobs and to minimize the total resource consumption cost in a two-machine flow-shop scheduling system. International Journal of Production Economics, 136(1), 67–74.CrossRef
Shafransky, Y. M., & Strusevich, V. A. (1998). The open shop scheduling problem with a given sequence of jobs on one machine. Naval Research Logistics, 45, 705–731.CrossRef
Sung, S. C., & Vlach, M. (2005). Maximizing weighted number of just-in-time jobs on unrelated parallel machines. Journal of Scheduling, 8(5), 453–460.CrossRef
Yin, Y., Cheng, S.-R., Cheng, T. C. E., Wang, D.-W., & Wu, C.-C. (2016). Just-in-time scheduling with two competing agents on unrelated parallel machines. Omega, 63, 41–47.CrossRef
Yin, Y., Cheng, T. C. E., Wang, D. J., & Wu, C. C. (2017). Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs. Journal of Scheduling, 20(4), 313–335.CrossRef
Metadata
Title
A note: maximizing the weighted number of Just-in-Time jobs for a given job sequence
Authors
Enrique Gerstl
Gur Mosheiov
Publication date
25-01-2023
Publisher
Springer US
Published in
Journal of Scheduling / Issue 4/2023
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI
https://doi.org/10.1007/s10951-022-00772-4

Other articles of this Issue 4/2023

Journal of Scheduling 4/2023 Go to the issue

OriginalPaper

A note on the shifting bottleneck procedure for job shop scheduling

OriginalPaper

Lot streaming for a two-stage assembly system in the presence of handling costs

OriginalPaper

Approximation algorithms for scheduling monotonic moldable tasks on multiple platforms

OriginalPaper

A multivariate complexity analysis of the material consumption scheduling problem

OriginalPaper

Exact and metaheuristic methods for a real-world examination timetabling problem