A new effective heuristic method for the no-wait flowshop with sequence-dependent setup times problem

International Journal of Industrial Engineering Computations

关键词: Scheduling;    Heuristic;    No-wait flowshop;    Sequence-dependent setup Makespan;   

DOI  :  

来源: DOAJ

【 摘 要 】

In this paper, we address the problem of scheduling jobs in a no-wait flowshop problem with sequence-dependent setup times with the objective of minimizing makespan. This problem is well-known for being nondeterministic polynomial-time hard, and small contribution to the problem has been made. We propose a new constructive heuristic named GAPH based on a structural property. The effectiveness of the structural property is crucial given that it is responsible for 100% of the success rate of the total problems tested. The computational results demonstrate that the proposed approach is superior than three of the best-know methods in the literature such as the twos by Bianco, Dell’Olmo and Giordani (INFOR Journal: 37 (1), 3-19, 1999) and TRIPS heuristic adapted for sequence-dependent setup times objective by Brown, Mcgarvey and Ventura (Journal of the Operational Research Society, 55 (6), 614-621, 2004) in terms of the solution quality and that it requires less computational effort.

【 授权许可】

Unknown