Groupe d’études et de recherche en analyse des décisions

Modeling and solving job shop scheduling problems with complex process features and complicated objectives

Reinhard Bürgy Polytechnique Montréal, Canada

The classical job shop scheduling problem (with makespan objective) is a fundamental problem in operations research. Numerous researchers have addressed this difficult optimization problem and a large body of knowledge has been accumulated on this topic. The applicability of the classical job shop problem is, however, limited in practice. Indeed, real-world problems typically possess complex process features that are not captured in the classical job shop, and the decision-makers often pursue more complicated objectives than the makespan.

In the first part of this talk, we introduce a combinatorial problem formulation of the classical job shop in a disjunctive graph, and we show how this formulation can be adapted to incorporate complex process features. In particular, we address sequence-dependent setup times, release times, no storage restrictions, time lags, routing flexibility, and transportation by mobile devices. We briefly discuss applications to train scheduling and scheduling of a production system with robots sharing a single rail line.

In the second part, we consider some objectives pursued in practice and consider the associated timing problems. In particular, we address the makespan objective, regular objectives, and convex cost objectives.

Finally, we sketch a local search solution approach that is based on job (re-) insertion. We first describe the job insertion problem and then develop a neighborhood based on local moves (an extension of the well-known swaps of critical operations) and a new concept called locally improving moves. We present numerical results supporting the validity of our approach.


Ce séminaire s'adresse seulement aux étudiants du GERAD.
Nous vous remercions de confirmer votre présence en indiquant votre nom complet. Des pizzas et des breuvages seront servis aux participants ou vous pouvez apporter votre lunch.