Producción Científica Profesorado

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



Seck Tuoh Mora, Juan Carlos

2014

J. C. Seck-Tuoh-Mora, L. Garcia-Lechuga, J. Medina-Marin ,N. Hernandez-Romero , E. S. Hernandez-Gress


Abstract


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



Producto de Investigación UAEH




Artículos relacionados

Pair Diagram and Cyclic Properties Characterizing the Inverse of Reversible Automata

Elementary cellular automaton Rule 110 explained as a block substitution system

Unconventional invertible behaviors in reversible one-dimensional cellular automata.

How to Make Dull Cellular Automata Complex by Adding Memory: Rule 126 Case Study

Modeling a Nonlinear Liquid Level System by Cellular Neural Networks

On explicit inversion of a subclass of operators with D-difference kernels and Weyl theory of the co...

Complex Dynamics Emerging in Rule 30 with Majority Memory

Reproducing the Cyclic Tag System Developed by Matthew Cook with Rule 110 Using the Phases f(i-)1.