4.7 Article

A parallel heuristic for hybrid job shop scheduling problem considering conflict-free AGV routing

期刊

SWARM AND EVOLUTIONARY COMPUTATION
卷 79, 期 -, 页码 -

出版社

ELSEVIER
DOI: 10.1016/j.swevo.2023.101312

关键词

Mixed Integer Linear Programming; Hybrid job shop scheduling; Conflict-free AGV routing; Parallel two-step decomposition-based; heuristic; Metaheuristics; Parallel computing

向作者/读者索取更多资源

A novel Parallel Two-Step Decomposition-Based Heuristic (PTSDBH) and Mixed Integer Linear Programming (MILP) have been developed to address the concurrent scheduling of jobs and Automated Guided Vehicles (AGVs) in a hybrid job shop system. The importance of conflict-free AGV routing has not been emphasized in previous studies, but it is crucial for preventing system breakdowns. PTSDBH, using parallel computing, is effective for solving large-sized problems quickly. Comparison with metaheuristics shows that PTSDBH outperforms them in terms of objective value quality, while TSDBH has higher runtimes due to its use of a single core. Statistical analysis confirms the superiority of PTSDBH and TSDBH over metaheuristics in terms of objective values.
In this study, a novel and computationally efficacious Parallel Two-Step Decomposition-Based Heuristic (PTSDBH) and a Mixed Integer Linear Programming (MILP) are developed to tackle the concurrent scheduling of jobs and Automated Guided Vehicles (AGVs) or transporters in a hybrid job shop system. Finite multiple AGVs, AGV eligibility, job's alternative process routes, job re-entry, and conflict-free AGV routing are considered. As far as the authors know, the importance of conflict-free routing for AGVs has not been featured in any of the past studies. Conflict-free AGV routing is an indispensable technicality, specifically where AGVs are the main mean of transportation as AGVs may collide on routes and the whole system ends up in breakdown. To avoid this issue, a conflict-free routing strategy is considered. Utilizing the parallel computing approach, PTSDBH is capable of tackling large-sized problems in remarkably shorter runtimes. To support this, PTSDBH is compared against three literarily well-known metaheuristics; i.e., Genetic Algorithm (GA), Particle Swarm Optimization (PSO), and Ant Colony Optimization (ACO) along with TSDBH (i.e., the single-core variant of PTSDBH) on three different-sized sets of benchmark instances. The results reveal that PTSDBH and TSDBH produce the same objective values and outperform the metaheuristics in terms of the quality of objective value. However, the runtimes of TSDBH are considerably higher than those of PTSDBH as it only uses one core to process. Finally, employing Nemenyi's post-hoc procedure for Friedman's test and the convergence plot, it is supported that the objective values generated by PTSDBH and TSDBH are significantly more desirable than those generated by the metaheuristics.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.7
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据