Local Search Procedures for Hybrid Flowshop Scheduling Problems with Due Date Windows

Autores UPV
Año
CONGRESO Local Search Procedures for Hybrid Flowshop Scheduling Problems with Due Date Windows

Abstract

Due dates are in reality more intervals than specific points in time. We study hybrid flowshops where jobs, when completed inside a due window, are considered on time. The objective is the minimization of the weighted earliness and tardiness from the due window. This objective has seldom been studied and there are almost no previous works for hybrid flowshops. We present methods based on the simple concepts of iterated greedy and iterated local search. We introduce some novel operators and characteristics, like an optimal idle time insertion procedure and a two stage local search where, in the second stage, a limited local search on a exact representation is carried out. We also present a comprehensive computational campaign, including the reimplementation and comparison of 9 competing procedures. A thorough evaluation of all methods with more than 3000 instances shows that our presented approaches yield superior results by a large margin which are also demonstrated to be statistically significant. Experiments also show the contribution of the new operators in the presented methods.