Comparing Iterative Improvement Heuristics for Multi-Capacity Scheduling Problems

Abstract

Iterative Flattening search is a local search schema introduced for solving scheduling problems with a makespan minimization objective. It is an iterative two-step procedure, where on each cycle of the search a subset of or-dering decisions on the critical path in the current solution are randomly retracted and then recomputed to produce a new solution. Since its introduction, other vari-ations have been explored and shown to yield substantial performance improve-ment over the original formulation. In this spirit, we propose and experimentally evaluate further improvements to this basic local search schema. Specifically, we examine the utility (1) of operating with a more flexible solution representation, (2) of adopting a more focused decision retraction strategy and (3) of integrating iterative-flattening search with a complementary tabu search procedure. We eval-uate these extensions on large benchmark instances of the Multi-Capacity Job-Shop Scheduling Problem (MCJSSP) which have been used in previous studies of iterative flattening search procedures.