Mathematical modeling and heuristic approaches to flexible job shop scheduling problems
Mathematical modeling and heuristic approaches to flexible job shop scheduling problems
复制标题
DOI：
10.1007/s10845-007-0026-8
复制
发表时间：
2007-06-01
影响因子：
8.3
通讯作者：
Jolai, Fariborz
中科院分区：
文献类型：
--
作者：
Fattahi, Parviz;Mehrabad, Mohammad Saidi;Jolai, Fariborz
柔性作业车间的调度在生产管理和组合优化领域都非常重要。然而，由于计算复杂度较高，传统的优化方法很难在中等规模和实际规模的问题上获得最优解。为了解决具有两个以上工作的实际情况，使用了两种方法：分层方法和集成方法。在分层方法中，对机器的操作分配和对资源或机器的操作排序是分开处理的，即，独立考虑分配和排序，而在集成方法中，分配和排序不区分。在本文中，考虑了灵活作业车间调度问题（FJSP）的数学模型和启发式方法。数学模型用于实现小规模问题的最优解。由于FJSP是NP难问题，因此开发了涉及集成和分层方法的两种启发式方法来解决实际尺寸问题。本文提出了六种不同的混合搜索结构，具体取决于所使用的搜索方法和启发式方法。数值实验用于评估所开发算法的性能。结论是，分层算法比集成算法具有更好的性能，并且连续使用禁忌搜索和模拟退火启发式来解决分配和排序问题的算法比其他算法更适合。数值实验还验证了所提出算法的质量。
Scheduling for the flexible job shop is very important in both fields of production management and combinatorial optimization. However, it is quite difficult to achieve an optimal solution to this problem in medium and actual size problem with traditional optimization approaches owing to the high computational complexity. For solving the realistic case with more than two jobs, two types of approaches have been used: hierarchical approaches and integrated approaches. In hierarchical approaches assignment of operations to machines and the sequencing of operations on the resources or machines are treated separately, i.e., assignment and sequencing are considered independently, where in integrated approaches, assignment and sequencing are not differentiated. In this paper, a mathematical model and heuristic approaches for flexible job shop scheduling problems (FJSP) are considered. Mathematical model is used to achieve optimal solution for small size problems. Since FJSP is NP-hard problem, two heuristics approaches involve of integrated and hierarchical approaches are developed to solve the real size problems. Six different hybrid searching structures depending on used searching approach and heuristics are presented in this paper. Numerical experiments are used to evaluate the performance of the developed algorithms. It is concluded that, the hierarchical algorithms have better performance than integrated algorithms and the algorithm which use tabu search and simulated annealing heuristics for assignment and sequencing problems consecutively is more suitable than the other algorithms. Also the numerical experiments validate the quality of the proposed algorithms.