New heuristics for no-wait flow shops with a linear combination of makespan and maximum lateness |
| |
Authors: | Rubén Ruiz Ali Allahverdi |
| |
Affiliation: | 1. Instituto Tecnológico de Informática, Universidad Politécnica de Valencia , Valencia, Spain rruiz@eio.upv.es;3. Department of Industrial and Management Systems Engineering , College of Engineering and Petroleum, Kuwait University , Safat, Kuwait |
| |
Abstract: | In this work we study a flow shop scheduling problem in which jobs are not allowed to wait between machines, a situation commonly referred to as no-wait. The criterion is to minimise a weighted sum of makespan and maximum lateness. A dominance relation for the case of three machines is presented and evaluated using experimental designs. Several heuristics and local search methods are proposed for the general m-machine case. The local search methods are based on genetic algorithms and iterated greedy procedures. An extensive computational analysis is conducted where it is shown that the proposed methods outperform existing heuristics and metaheuristics in all tested scenarios by a considerable margin and under identical CPU times. |
| |
Keywords: | scheduling heuristics makespan metaheuristics modelling math programming flow lines flow shop flow shop scheduling genetic algorithms |
|