Skip to main content
Top
Published in: Journal of Scheduling 6/2020

18-07-2019

Flowshop scheduling with learning effect and job rejection

Authors: Baruch Mor, Gur Mosheiov, Dana Shapira

Published in: Journal of Scheduling | Issue 6/2020

Log in

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

search-config
loading …

Abstract

We study scheduling problems on a proportionate flowshop. Three objective functions are considered: minimum makespan, minimum total completion time, and minimum total load. We consider a learning process; thus, the processing time of a job processed later in sequence is reduced. The scheduler has the option of job rejection; i.e., only a subset of the jobs are processed and the rejected jobs are penalized. An upper bound on the total permitted rejection cost is assumed. Since the single-machine versions of these problems were shown to be NP-hard, we focus on the introduction of pseudopolynomial dynamic programming algorithms, indicating that the problems are NP-hard in the ordinary sense. We provide an extensive numerical study verifying that the proposed solution algorithms are very efficient and instances containing up to 80 jobs are solved in no more than 5 ms.

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!

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!

Literature
go back to reference Agnetis, A., & Mosheiov, G. (2017). Scheduling with job-rejection and position-dependent processing times on proportionate flowshops. Optimization Letters, 11, 885–892.CrossRef Agnetis, A., & Mosheiov, G. (2017). Scheduling with job-rejection and position-dependent processing times on proportionate flowshops. Optimization Letters, 11, 885–892.CrossRef
go back to reference Azzouz, A., Ennigrou, M., & Ben Said, L. (2018). Scheduling problems under learning effects: Classification and cartography. International Journal of Production Research, 56, 1642–1661.CrossRef Azzouz, A., Ennigrou, M., & Ben Said, L. (2018). Scheduling problems under learning effects: Classification and cartography. International Journal of Production Research, 56, 1642–1661.CrossRef
go back to reference Biskup, D. (1999). Single-machine scheduling with learning considerations. European Journal of Operational Research, 115, 173–178.CrossRef Biskup, D. (1999). Single-machine scheduling with learning considerations. European Journal of Operational Research, 115, 173–178.CrossRef
go back to reference Biskup, D. (2008). A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research, 188, 315–329.CrossRef Biskup, D. (2008). A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research, 188, 315–329.CrossRef
go back to reference Epstein, E., & Zebedat-Haider, H. (2016). Online scheduling of unit jobs on three machines with rejection: A tight result. Information Processing Letters, 116, 252–255.CrossRef Epstein, E., & Zebedat-Haider, H. (2016). Online scheduling of unit jobs on three machines with rejection: A tight result. Information Processing Letters, 116, 252–255.CrossRef
go back to reference Fiszman, S., & Mosheiov, G. (2018). Minimizing total load on a proportionate flowshop with position-dependent processing times and job rejection. Information Processing Letters, 132, 39–43.CrossRef Fiszman, S., & Mosheiov, G. (2018). Minimizing total load on a proportionate flowshop with position-dependent processing times and job rejection. Information Processing Letters, 132, 39–43.CrossRef
go back to reference Gawiejnowicz, S. (1996). A note on scheduling on a single processor with speed dependent on a number of executed jobs. Information Processing Letters, 57, 297–300.CrossRef Gawiejnowicz, S. (1996). A note on scheduling on a single processor with speed dependent on a number of executed jobs. Information Processing Letters, 57, 297–300.CrossRef
go back to reference Gerstl, E., Mor, B., & Mosheiov, G. (2017). Minmax scheduling with acceptable lead-times: Extensions to position-dependent processing times, due-window and job rejection. Computers & Operations Research, 83, 150–156.CrossRef Gerstl, E., Mor, B., & Mosheiov, G. (2017). Minmax scheduling with acceptable lead-times: Extensions to position-dependent processing times, due-window and job rejection. Computers & Operations Research, 83, 150–156.CrossRef
go back to reference Gerstl, E., & Mosheiov, G. (2017). Single machine scheduling problems with generalised due-dates and job-rejection. International Journal of Production Research, 55, 3164–3172.CrossRef Gerstl, E., & Mosheiov, G. (2017). Single machine scheduling problems with generalised due-dates and job-rejection. International Journal of Production Research, 55, 3164–3172.CrossRef
go back to reference Hill, C. W. L. (2016). International business: Competing in the global marketplace (6th ed.). New York: McGraw-Hill. Hill, C. W. L. (2016). International business: Competing in the global marketplace (6th ed.). New York: McGraw-Hill.
go back to reference Mor, B., & Mosheiov, G. (2016). Minimizing maximum cost on a single machine with two competing agents and job rejection. Journal of the Operational Research Society, 67, 1524–1531.CrossRef Mor, B., & Mosheiov, G. (2016). Minimizing maximum cost on a single machine with two competing agents and job rejection. Journal of the Operational Research Society, 67, 1524–1531.CrossRef
go back to reference Mor, B., & Mosheiov, G. (2018). A note: Minimizing total absolute deviation of job completion times on unrelated machines with general position-dependent processing times and job-rejection. Annals of Operations Research, 271, 1079–1085.CrossRef Mor, B., & Mosheiov, G. (2018). A note: Minimizing total absolute deviation of job completion times on unrelated machines with general position-dependent processing times and job-rejection. Annals of Operations Research, 271, 1079–1085.CrossRef
go back to reference Mosheiov, G. (2001). Scheduling problems with a learning effect. European Journal of Operational Research, 132, 687–693.CrossRef Mosheiov, G. (2001). Scheduling problems with a learning effect. European Journal of Operational Research, 132, 687–693.CrossRef
go back to reference Mosheiov, G., & Strusevich, V. (2017). Determining optimal sizes of bounded batches with rejection via quadratic min-cost flow. Naval Research Logistics, 64, 217–224.CrossRef Mosheiov, G., & Strusevich, V. (2017). Determining optimal sizes of bounded batches with rejection via quadratic min-cost flow. Naval Research Logistics, 64, 217–224.CrossRef
go back to reference Ou, J., Zhong, X., & Li, C. L. (2016). Faster algorithms for single machine scheduling with release dates and rejection. Information Processing Letters, 116, 503–507.CrossRef Ou, J., Zhong, X., & Li, C. L. (2016). Faster algorithms for single machine scheduling with release dates and rejection. Information Processing Letters, 116, 503–507.CrossRef
go back to reference Ou, J., Zhong, X., & Wang, G. (2015). An improved heuristic for parallel machine scheduling with rejection. European Journal of Operational Research, 241, 653–661.CrossRef Ou, J., Zhong, X., & Wang, G. (2015). An improved heuristic for parallel machine scheduling with rejection. European Journal of Operational Research, 241, 653–661.CrossRef
go back to reference Shabtay, D., Gaspar, N., & Kaspi, M. (2013). A survey on offline scheduling with rejection. Journal of Scheduling, 16, 3–28.CrossRef Shabtay, D., Gaspar, N., & Kaspi, M. (2013). A survey on offline scheduling with rejection. Journal of Scheduling, 16, 3–28.CrossRef
go back to reference Shabtay, D., Karhi, S., & Oron, D. (2015). Multipurpose scheduling with rejection and job processing times. Journal of Scheduling, 18, 75–88.CrossRef Shabtay, D., Karhi, S., & Oron, D. (2015). Multipurpose scheduling with rejection and job processing times. Journal of Scheduling, 18, 75–88.CrossRef
go back to reference Thevenin, S., Zufferey, N., & Widmer, M. (2015). Metaheuristics for a scheduling problem with rejection and tardiness penalties. Journal of Scheduling, 18, 89–105.CrossRef Thevenin, S., Zufferey, N., & Widmer, M. (2015). Metaheuristics for a scheduling problem with rejection and tardiness penalties. Journal of Scheduling, 18, 89–105.CrossRef
go back to reference Zhang, L., Lu, L., & Yuan, J. (2010). Single-machine scheduling under the job rejection constraint. Theoretical Computer Science, 411, 1877–1882.CrossRef Zhang, L., Lu, L., & Yuan, J. (2010). Single-machine scheduling under the job rejection constraint. Theoretical Computer Science, 411, 1877–1882.CrossRef
go back to reference Zhong, X., Pan, Z., & Jiang, D. (2017). Scheduling with release times and rejection on two parallel machines. Journal of Combinatorial Optimization, 33, 934–944.CrossRef Zhong, X., Pan, Z., & Jiang, D. (2017). Scheduling with release times and rejection on two parallel machines. Journal of Combinatorial Optimization, 33, 934–944.CrossRef
Metadata
Title
Flowshop scheduling with learning effect and job rejection
Authors
Baruch Mor
Gur Mosheiov
Dana Shapira
Publication date
18-07-2019
Publisher
Springer US
Published in
Journal of Scheduling / Issue 6/2020
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI
https://doi.org/10.1007/s10951-019-00612-y

Other articles of this Issue 6/2020

Journal of Scheduling 6/2020 Go to the issue