Open Shop Scheduling Problems

BEA528 Open Shop Scheduling Problems

Autumn 2025

  • 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

Overview

ECTS Credits
2.5
Teaching language
English
Teaching Semester

Autumn. Not offered autumn 2025

Course responsible

Prof Stein W. Wallace, Business and Management Science