Permutation flowshop problems minimizing core waiting time and core idle time. (February 2023) - Alfieri, Arianna
Abstract: Waiting time and idle time are among the main cost sources in production systems. They can also affect the feasibility of operations from a technological perspective; hence, both such times have to be kept as small as possible. This paper studies four single-objective variants of the permutation flowshop scheduling problem, where two objectives are considered: the weighted sum of the makespan and the core waiting time, and the weighted sum of the makespan and the core idle time. For each objective, both the problem with the assumption of semi-active solution and the one without it are considered. A general solution framework for tackling the above-mentioned problems is provided. First, two Mixed Integer Linear Programming (MILP) formulations (based on positional and precedence variables, respectively) and one Constraint Programming (CP) formulation are presented. Second, a MILP-based local search approach based on the positional MILP formulation and the concept of sliding windows are defined. An extensive set of computational experiments on benchmark instances show that the positional MILP formulation strongly outperforms the other two formulations in all the considered cases. The experiments also show that the sliding window local search heuristic achieves much better performances than other state-of-the-art local search heuristics. Indeed, it is able to improve the state-of-the-art in 2384 instances out of 2400. Highlights: The permutation flowshop scheduling problem is considered. Core Waiting and Idle Times are minimized, with semi-active and general schedules. Two MILPs and a CP models are formalized. A sliding window local search is developed and compared with state-of-the-art. Extensive experiments prove the efficiency of the proposed approach.