Improving the Multi-Restart Local Search Algorithm byPermutation Matrices and Sorted Completion Times for the Flow Shop Scheduling Problem

Iterated local search (ILS) is a metaheuristicused successfully to solve the flow shop scheduling problem.In particular, the multi-restart ILS (MRSILS) is an easilyimplementable algorithm which obtains good results. Inthis paper, we modify the MRSILS algorithm in two ways.First, small changes in the initial solution are generated bypermutation matrices in order to improve it before using theMRSILS. Second, a minor variation is made in the strategyof the MRSILS. Sorted completion times are taken to selectthe job to be inserted in new positions to obtain a betterscheduling. The original MRSILS and both modificationsare evaluated with well-known benchmark instances. Theexperiments show that the new modifications produce slightlybetter results than the original one, especially for a largenumber of jobs