BEA528 Open Shop Scheduling Problems

• Topics

  Cruise companies can greatly benefit from offering passengers well-curated touristic recommendations and itineraries that maximize their experience while ensuring they return to the ship on time. However, from the perspective of the city hall, it's important to achieve a more even distribution of visitors across the city to avoid overcrowding. According to Bergen’s urbanization plan, there are specific areas where it is preferable to direct visitors to support urban development, social welfare, and environmental sustainability.

  The challenge of balancing these interests can be modeled as a unique case of the Open Shop Scheduling Problem, a notoriously complex scheduling issue. The difficulty lies in the vast search space, as the almost unlimited combination possibilities create an overwhelming number of options. As a result, exact mathematical solutions using state-of-the-art algorithms have proven ineffective. Instead, the literature has explored alternative approaches, primarily focusing on meta-heuristics to tackle this problem.

  The proposed reading course will address the complexity of scheduling problems and provide an overview of algorithms and meta-heuristics used to solve large instances of such problems.

• Learning outcome

  After completing the course, the candidates can

  Knowledge

  • gain a deeper understanding of scheduling problems and the algorithms used to find either exact solutions or efficient approximations

  Skills

  • build a strong foundation in this sub-field to develop and propose a solution approach as part of the PhD thesis.
  • enhance computational skills necessary for implementing the proposed solution.

• Teaching

  Reading course with regular meetings with instructor

• Restricted access

  PhD candidates at NHH only

• Recommended prerequisites

  Advanced knowledge on operations management and operations research.

  Previous knowledge on machine learning and meta-heuristics

• Assessment

  Write a term paper exploring methodologies for solving Open Shop Scheduling Problems, focusing on how these can optimize touristic itineraries for cruise visitors in Bergen. The student must propose a solution strategy to address the stated problem and the specific challenges in Bergen.

• Grading Scale

  Pass/fail

• Computer tools

  Python or C++ programming languages

• Literature

  Tsirlin, A., & Balunov, A. (2022). Job-shop scheduling problem and its solution method. Research Square, 1. https://doi.org/10.21203/rs.3.rs-2294412/v1https://doi.org/10.21203/rs.3.rs-2294412/v1

  Woeginger, G. J. (2018). The open shop scheduling problem. 4, 4:1-4:12. https://doi.org/ 10.4230/LIPIcs.STACS.2018.4

  Medhat, W., Hassan, A., & Korashy, H. (2014). Sentiment analysis algorithms and applications: A survey. Science Direct, 5, 1093-1113. https://doi.org/10.1016/j.%20asej.2014.04.011https://doi.org/10.1016/j. asej.2014.04.011

  Li, W., Ding, Y., Yang, Y., Sherratt, R. S., Park, J. H., & Wang, J. (2020). Parameterized algorithms of fundamental NP-hard problems: A survey. Springer Link, 10. https: //doi.org/10.1186/s13673-020-00226-w

  Kubiak, W. (2022). A book of open shop scheduling: Algorithms, complexity and applications (1st ed.). 325. https://doi.org/10.1007/978-3-030-91025-9https://doi.org/10.1007/978-3-030-91025-9

  Du, P., Liu, N., Zhang, H., & Lu, J. (2021). An improved ant colony optimization based on an adaptive heuristic factor for the traveling salesman problem. Hindawi, 2021. https://doi.org/10.1155/2021/6642009https://doi.org/10.1155/2021/6642009

  Brucker, P., Sotskov, Y. N., & Werner, F. (2007). Complexity of shop-scheduling problems with fixed number of jobs: A survey. ResearchGate, 65, 461-481. https://doi.org/ 10.1007/s00186-006-0127-8