دانلود رایگان مقاله بهینه سازی مگاپن برای مساله برنامه ریزی فلاوشاپ بدون انتظار با استفاده از مفاهیم کارآمد

abstract

The no-wait flowshop scheduling problem (NWFSP) with makespan minimization is a well-known strongly NP-hard problem with applications in various industries. This study formulates this problem as an asymmetric traveling salesman problem, and proposes two matheuristics to solve it. The performance of each of the proposed matheuristics is compared with those of the best existing algorithms on 21 benchmark instances of Reeves and 120 benchmark instances of Taillard. Computational results show that the presented matheuristics outperform all existing algorithms. In particular, all tested instances of the problem, including a subset of 500-job and 20-machine test instances, are solved to optimality in an acceptable computational time. Moreover, the proposed matheuristics can solve very hard and large NWFSPs to optimality, including the benchmark instances of Vallada et al. and a set of 2000-job and 20- machine problems. Accordingly, this study provides a feasible means of solving the NP-hard NWFSP completely and effectively.

5. Conclusions and recommendations for future studies

The Fm j nwtj Cmax problem that is studied herein arises often in many industries. Finding an optimal solution to the Fm j nwtj Cmax problem has long been a challenging task, in spite of the fact that the problem is so extensively studied. This study proposes two matheuristics to solve this problem effectively and efficiently. Experiments on four benchmark problem sets reveal that the proposed matheuristics yield optimal solutions for very large test instances in an acceptable computational time. This fact demonstrates the main contribution provided by the proposed matheuristics, especially since the problem is NP-hard in the strong sense. The optimality of the solution and the modest computational requirement make the proposed matheuristics highly valuable for use in practical manufacturing systems, thus bridging the gap between research and practice.