Seminar: Modeling and solving job shop problems with complex process features and complicated objectives
Author: Reinhard Bürgy
About the author:
Reinhard Bürgy is a postdoctoral researcher at Polytechnique Montreal and GERAD. He received a Ph.D. in Economics and Social Sciences from University of Fribourg, Switzerland, in 2014, and joined Polytechnique Montreal in Nov 2015 where he is currently working in the group of Prof. Alain Hertz. Reinhard’s current research interests are in bridging the gap between theory and practice in job shop scheduling by developing generic models, methods and decision support systems. Furthermore, he has a broad interest in mathematical modeling, combinatorial optimization, operations management and revenue management.
Presentation:
Abstract:
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.
