Back
Texte intégral
Doctoral thesis

Complex job shop scheduling : Formulations, algorithms and a healthcare application

    19.02.2008

162 p

Thèse de doctorat: Université de Fribourg, 2008

English This dissertation studies complex job shop scheduling problems. It consists of three coherent parts: (1) a study of practical features of job shop scheduling, (2) a study of a novel job shop extension problem that simultaneously addresses several practical features and its solution methods, and (3) a study of surgical case scheduling in hospitals and ambulatory surgical centers. A job shop problem in practice often possesses one or several complexifying features that are not addressed in the classical job shop (JS) model. In the first part of this dissertation, various practical features of job shop scheduling are systematically analyzed. In addition, we formulate a number of job shop problems extended with a single additional feature as mixed integer linear programming (MILP) problems, which can be used as building blocks to formulate more complex job shop problems. To evaluate the practical use of the exact method with MILP formulation and CPLEX solver as a representative for general-purpose solvers for solving different job shop related problems, we carry out comprehensive computational experiments on benchmark data. In the second part of the dissertation, a new job shop extension is proposed, which integrates into the JS four complexifying features namely processor exibility, blocking constraints, sequencedependent setup times, and job transfer times. This extension is called the Flexible Generalized Blocking Job Shop problem (FGBJS), which is capable of modeling many complex real world scheduling problems but very diffcult to solve. To develop solution methods for the FGBJS, we first formulate the problem as a MILP, then solve the problem heuristically since the performance of the exact method by a MILP formulation and CPLEX solver is not good. We propose a graph representation for the FGBJS and develop three neighbor structures allowing to generate neighbor solutions by moving an operation in time and from a processor to another. Using these neighborhoods and job insertion principles, we develop three constructive heuristics. To improve a given FGBJS solution, we propose six Tabu search (TS) heuristics that result from combining the three neighborhood structures and three generic TS algorithms. Extensive computational results of these constructive and TS heuristics on 160 newly created FGBJS instances are given, which can be used to benchmark other solution methods for the FGBJS in the future. The last part of the dissertation tackles surgical case scheduling (SCS). This is an important problem in healthcare management because of the financial impact of surgical activities in hospitals and ambulatory surgical centers (ASC). We analyze the patient ow, model the problem accordingly as a new job shop extension called the multimode blocking job shop (MMBJS), and give a MILP formulation for the MMBJS. While developing efficient solution methods for the MMBJS is still in progress, we can show that it is possible to model the SCS in ASC as a FGBJS because of several particular operational features. Further, we identify certain conditions upon which the SCS in hospitals can also be modeled as the FGBJS. In these cases, one can apply the solution methods developed in the second part of the dissertation to solve the SCS.
Faculty
Faculté des sciences économiques et sociales et du management
Department
Département d'informatique
Language
  • English
Classification
Information, communication and media sciences
Notes
  • Ressource en ligne consultée le 26.02.2008
License
License undefined
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/300454
Statistics
Document views: 146 File downloads:
  • PhamDN.pdf: 85