Movatterモバイル変換


[0]ホーム

URL:


Skip to main content

Advertisement

Springer Nature Link
Log in

A Variable Neighborhood Search for the Job Sequencing with One Common and Multiple Secondary Resources Problem

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 12270))

Included in the following conference series:

Abstract

In this work we consider a scheduling problem where a set of non-preemptive jobs needs to be scheduled such that the makespan is minimized. Each job requires two resources: (1) a common resource, shared by all jobs and (2) a secondary resource, shared with only a subset of the other jobs. The secondary resource is required during the job’s entire processing time whereas the common resource is only required during a part of a job’s execution. The problem models, for instance, the scheduling of patients during one day in a particle therapy facility for cancer treatment. We heuristically tackle the problem by a general variable neighborhood search (GVNS) based on move and exchange neighborhoods and an efficient evaluation scheme to scan the neighborhoods of the current incumbent solution. An experimental evaluation on two benchmark instance sets, including instances with up to 2000 jobs, shows the effectiveness of the GVNS. In particular for larger instances our GVNS outperforms an anytime A\(^*\) algorithm that was the so far leading method in heuristic terms as well as a constrained programming model solved by ILOG CP optimizer.

We gratefully acknowledge the financial support of the Doctoral Program “Vienna Graduate School on Computational Optimization” funded by Austrian Science Foundation under Project No W1260-N35.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11210
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14013
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Similar content being viewed by others

References

  1. Conforti, D., Guerriero, F., Guido, R.: Optimization models for radiotherapy patient scheduling. 4OR6(3), 263–278 (2008)

    Article MathSciNet  Google Scholar 

  2. Hansen, P., Mladenović, N., Pérez, J.A.M.: Variable neighbourhood search: methods and applications. Ann. Oper. Res.175(1), 367–407 (2010)

    Article MathSciNet  Google Scholar 

  3. Hansen, P., Mladenović, N., Todosijević, R., Hanafi, S.: Variable neighborhood search: basics and variants. EURO J. Comput. Optim.5(3), 423–454 (2016).https://doi.org/10.1007/s13675-016-0075-x

    Article MathSciNet MATH  Google Scholar 

  4. Horn, M., Maschler, J., Raidl, G., Rönnberg, E.: A*-based construction of decision diagrams for a prize-collecting scheduling problem. Technical report AC-TR-18-011, Algorithms and Complexity Group, TU Wien (2018)

    Google Scholar 

  5. Horn, M., Raidl, G., Blum, C.: Job sequencing with one common and multiple secondary resources: an A*/Beam Search based anytime algorithm. Artif. Intell.277(103173) (2019)

    Google Scholar 

  6. Horn, M., Raidl, G., Rönnberg, E.: A* search for prize-collecting job sequencing with one common and multiple secondary resources. Ann. Oper. Res. (2020)

    Google Scholar 

  7. Horn, M., Raidl, G.R., Rönnberg, E.: An A\(^*\) algorithm for solving a prize-collecting sequencing problem with one common and multiple secondary resources and time windows. In: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling, PATAT 2018, pp. 235–256 (2018)

    Google Scholar 

  8. Horn, M., Raidl, G., Blum, C.: Job sequencing with one common and multiple secondary resources: a problem motivated from particle therapy for cancer treatment. In: Nicosia, G., Pardalos, P., Giuffrida, G., Umeton, R. (eds.) MOD 2017. LNCS, vol. 10710, pp. 506–518. Springer, Cham (2018).https://doi.org/10.1007/978-3-319-72926-8_42

    Chapter  Google Scholar 

  9. Kapamara, T., Sheibani, K., Haas, O., Petrovic, D., Reeves, C.: A review of scheduling problems in radiotherapy. In: Proceedings of the International Control Systems Engineering Conference, pp. 207–211. Coventry University Publishing (2006)

    Google Scholar 

  10. Kaufmann, T.: A variable neighborhood search for the job sequencing with one common and multiple secondary resources problem. Master’s thesis, TU Wien, Vienna, Austria (2019)

    Google Scholar 

  11. López-Ibáńez, M., Dubois-Lacoste, J., Pérez Cáceres, L., Stützle, T., Birattari, M.: The irace package: iterated racing for automatic algorithm configuration. Oper. Res. Perspect.3, 43–58 (2016)

    Article MathSciNet  Google Scholar 

  12. Maschler, J., Raidl, G.R.: Multivalued decision diagrams for a prize-collecting sequencing problem. In: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling, PATAT 2018, pp. 375–397 (2018)

    Google Scholar 

  13. Maschler, J., Riedler, M., Stock, M., Raidl, G.R.: Particle therapy patient scheduling: first heuristic approaches. In: Proceedings of the 11th International Conference of the Practice and Theory of Automated Timetabling, PATAT 2016, pp. 223–244 (2016)

    Google Scholar 

  14. Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res.24(11), 1097–1100 (1997)

    Article MathSciNet  Google Scholar 

  15. Schiavinotto, T., Stützle, T.: A review of metrics on permutations for search landscape analysis. Comput. Oper. Res.34(10), 3143–3153 (2007).https://doi.org/10.1016/j.cor.2005.11.022

    Article MATH  Google Scholar 

  16. Van der Veen, J.A.A., Wöginger, G.J., Zhang, S.: Sequencing jobs that require common resources on a single machine: a solvable case of the TSP. Math. Program.82(1–2), 235–254 (1998)

    MathSciNet MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Logic and Computation, TU Wien, Vienna, Austria

    Thomas Kaufmann, Matthias Horn & Günther R. Raidl

Authors
  1. Thomas Kaufmann

    You can also search for this author inPubMed Google Scholar

  2. Matthias Horn

    You can also search for this author inPubMed Google Scholar

  3. Günther R. Raidl

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toMatthias Horn.

Editor information

Editors and Affiliations

  1. Leiden University, Leiden, The Netherlands

    Thomas Bäck

  2. Leiden University, Leiden, The Netherlands

    Mike Preuss

  3. Leiden University, Leiden, The Netherlands

    André Deutz

  4. Sorbonne University, Paris, France

    Hao Wang

  5. Sorbonne University, Paris, France

    Carola Doerr

  6. Leiden University, Leiden, The Netherlands

    Michael Emmerich

  7. University of Münster, Münster, Germany

    Heike Trautmann

Rights and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Kaufmann, T., Horn, M., Raidl, G.R. (2020). A Variable Neighborhood Search for the Job Sequencing with One Common and Multiple Secondary Resources Problem. In: Bäck, T.,et al. Parallel Problem Solving from Nature – PPSN XVI. PPSN 2020. Lecture Notes in Computer Science(), vol 12270. Springer, Cham. https://doi.org/10.1007/978-3-030-58115-2_27

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11210
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14013
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only


[8]ページ先頭

©2009-2025 Movatter.jp