Hybrid Flow Shop with Setup Times Scheduling Problem |
| |
| Authors: | Mahdi Jemmali Lotfi Hidri |
| |
| Affiliation: | School of Computer Science and Engineering, Vellore Institute of Technology, Chennai, 600127, India |
| |
| Abstract: | The two-stage hybrid flow shop problem under setup times is addressed in this paper. This problem is NP-Hard. on the other hand, the studied problem is modeling different real-life applications especially in manufacturing and high performance-computing. Tackling this kind of problem requires the development of adapted algorithms. In this context, a metaheuristic using the genetic algorithm and three heuristics are proposed in this paper. These approximate solutions are using the optimal solution of the parallel machines under release and delivery times. Indeed, these solutions are iterative procedures focusing each time on a particular stage where a parallel machines problem is called to be solved. The general solution is then a concatenation of all the solutions in each stage. In addition, three lower bounds based on the relaxation method are provided. These lower bounds present a means to evaluate the efficiency of the developed algorithms throughout the measurement of the relative gap. An experimental result is discussed to evaluate the performance of the developed algorithms. In total, 8960 instances are implemented and tested to show the results given by the proposed lower bounds and heuristics. Several indicators are given to compare between algorithms. The results illustrated in this paper show the performance of the developed algorithms in terms of gap and running time. |
| |
| Keywords: | Hybrid flow shop genetic algorithm setup times heuristics lower bound |
|
| 点击此处可从《计算机系统科学与工程》浏览原始摘要信息 |
|
点击此处可从《计算机系统科学与工程》下载全文 |
|
