A tutorial survey of job-shop scheduling problems using genetic algorithms—I: representation
A tutorial survey of job-shop scheduling problems using genetic algorithms—I: representation
复制标题
DOI：
10.1016/0360-8352(96)00047-2
复制
发表时间：
1996-09
影响因子：
7.9
通讯作者：
Runwei Cheng;M. Gen;Y. Tsujimura
中科院分区：
文献类型：
--
作者：
Runwei Cheng;M. Gen;Y. Tsujimura
作业车间调度问题（Job-shop scheduling problem，简称JSP）是著名的最难组合优化问题之一。在过去的三十年里，这个问题已经引起了大量研究人员的兴趣，并发表了大量的文献，但还没有找到有效的解决算法来解决它的最优性在多项式时间。这导致了最近的兴趣，使用遗传算法（GAs）来解决it. The本文及其同伴（第二部分：混合遗传搜索策略）的目的是给一个教程调查最近的作品解决经典JSP使用遗传算法。在第一部分中，我们把注意力集中在JSP的表示方案上。在第二部分中，我们将讨论遗传算法和传统算法的各种混合方法。GA/JSP的研究工作为约束组合优化问题提供了非常丰富的经验。为JSP开发的所有技术可能对现代柔性制造系统中的其他调度问题和其他组合优化问题有用。
Job-shop scheduling problem (abbreviated to JSP) is one of the well-known hardest combinatorial optimization problems. During the last three decades, the problem has captured the interest of a significant number of researchers and a lot of literature has been published, but no efficient solution algorithm has been found yet for solving it to optimality in polynomial time. This has led to recent interest in using genetic algorithms (GAs) to address it. The purpose of this paper and its companion (Part II: Hybrid Genetic Search Strategies) is to give a tutorial survey of recent works on solving classical JSP using genetic algorithms. In Part I, we devote our attention to the representation schemes proposed for JSP. In Part II, we will discuss various hybrid approaches of genetic algorithms and conventional heuristics. The research works on GA/JSP provide very rich experiences for the constrained combinatorial optimization problems. All of the techniques developed for JSP may be useful for other scheduling problems in modern flexible manufacturing systems and other combinatorial optimization problems.