Title: Complex job shop with regular objective: Narrowing the gap between theory and practice in job shop scheduling

Speaker: Reinhard Bürgy – Polytechnique Montréal, Canada

Abstract:

In the last years, job shop scheduling problems that are more complex but also of wider applicability than the classical job shop have found increasing interest. These problems include additional process features such as limited storage capacity, routing flexibility, setup times, and time lags. While several methods have been developed for various complex job shop scheduling problems, most of them consider as objective makespan minimization and few address other objectives, for example objectives related to flow times or due dates, which are equally relevant in practice.

In this talk, we address a general complex job shop scheduling problem with arbitrary regular objective. We give a disjunctive graph formulation of the problem and develop a local search solution method using a neighborhood based on job-insertion theory. A key feature is the ability to consistently and efficiently generate feasible neighbor solutions, typically by moving a critical operation together with other operations whose moves are 'implied'.

Numerical results are presented for the job shop, the job shop with setup times, and the blocking job shop and the following six objectives: makespan, total flow time, total squared flow time, total tardiness, total weighted tardiness, and number of tardy jobs. The obtained results support the validity of the proposed method.

Free entrance.
Welcome to everyone!