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

The blocking job-shop scheduling problem with total tardiness objective: Mathematical programming formulations and a simulated annealing heuristic

Julia Lange Otto-von-Guericke-Universität Magdeburg, Allemagne

The job-shop scheduling problem, which models the production of customized goods, is one of the standard optimization problems in scheduling research. A limited applicability of the classical job-shop problem in practice has motivated the study of richer variants that include additional process features and practically relevant optimization criteria. In this talk, a job-shop scheduling problem characterized by blocking constraints and a total tardiness objective is considered. Blocking constraints implement a lack of buffers in the production or logistics system. These restrictions occur, for instance, in the production of huge items as well as in single-track railway scheduling. The tardiness-based objective is especially suitable when modeling economic purposes such as contract compliance and customer due date targets. The problem under study is not only NP-hard but also particularly challenging due to feasibility issues caused by the absence of buffers. Two mixed-integer linear programming (MILP) formulations for the blocking job-shop problem are described and compared. However, since current state-of-the-art solvers struggle in solving the MILPs even for small instances, a simulated annealing heuristic is additionally introduced, which obtains good solutions within reasonable computation times. A focus is placed on the discussion of the neighborhood definition as generating feasible neighbors causes significant difficulties. The talk is concluded by sketching a matheuristic solution method, which is under development in a current project.

Entrée gratuite.
Bienvenue à tous!