Hybrid Intelligent Algorithm for Flexible Job-Shop Scheduling Problem under Uncertainty
Hybrid Intelligent Algorithm for Flexible Job-Shop Scheduling Problem under Uncertainty
复制标题
DOI：
10.5772/13195
复制
发表时间：
2011-01
期刊：
影响因子：
--
通讯作者：
Guojun Zhang;Haiping Zhu;Chaoyong Zhang
中科院分区：
文献类型：
--
作者：
Guojun Zhang;Haiping Zhu;Chaoyong Zhang
生产调度在提高生产效率、降低生产成本方面起着重要的作用。其核心技术之一是建立有效的调度模型及其相应的优化算法。然而，目前的研究大多集中在静态环境下的调度优化，对真实的车间调度的不确定性和复杂性关注较少。在调度问题中，如果忽略或不考虑加工时间的变化、存储能力的不确定性、人为决策的可能性、不可预测的事故等情况，那么调度问题的精确解就与实际调度问题的精确解不同。随着相关领域和优化理论的发展，大量的方法和技术被引入到JSP中。运筹学将作业调度问题转化为数学规划模型，利用分支定界法和动态规划算法实现最优或近似最优。然而，OR仅适用于简单的调度问题（Philips等人，1987年）。格什温等人以控制理论为基础，全面阐述了控制理论在制造系统中的应用。受限于建模能力，必须对环境进行大量的简化;获得最优解的实践以指数特征扩展（Juanqi，1998）。人工智能（Artificial Intelligence，AI）是JSP调度方法的综合，旨在提高调度方法的智能性。它可以弥补数学规划和仿真的不足。基于系统状态和确定的优化目标，进行有效的启发式搜索和并发模糊推理，选择最优解，支持在线决策。然而，人工智能对新环境的适应能力较弱，这种方法主要有三个局限性：运算速度慢，对环境中的突发事件不敏感，系统不能普遍采用（Juanqi，1998）。在车间离散事件动态系统中，JSP可以
Production scheduling plays an important role in improving efficiency and reducing cost. One of its core technologies is the establishment of an effective scheduling model and its corresponding optimization algorithms. However, most researches focus on scheduling optimization in static environment, less concern of the uncertainty and complexity in the real job-shop. It must be different from the exact solution if some situations are ignored or not considered in scheduling problem such as changing processing time, uncertain capability of storage, possibility of human decision, unpredicted accident and so on. Inchoate research on FJSP (Flexible Job-Shop Scheduling Problem) concentrated on the simple application of integer programming and simulation, which can hardly be used to solve the complex scheduling problem. With the development of related fields and theory of optimization, a great many methods and techniques have been adopted into JSP. Operational research predigests the JSP into a mathematical programming model, using branch-and-bound method and dynamic programming algorithm to realize optimization or approximate optimization. However, OR only suits to simple scheduling problem (Philips et al., 1987). Based on theory of control, Gershwin and his fellows expatiate comprehensively the adoption of theory of control in manufacturing system. Limited to the capability of modeling, a lot of predigestion to the environment is a must; the practice to get the optimum solution expands with a exponential characteristic (Juanqi, 1998). AI (Artificial Intelligence) is a combination of all the methods for JSP, which aim at enhancing the intelligence of scheduling method. It can smooth the disadvantages of mathematical programming and simulation. Based on the system status and deterministic objective of optimization, effective heuristic research and concurrent fuzzy reasoning are conducted to choose the optimum solution and support online decision. Nevertheless, AI is weak in adapting to new environment, and there are 3 main limitations of this method: low speed of operation, insensitive to asynchronisic event in the environment, the system can’t be universally adopted (Juanqi, 1998). In a job-shop DEDS (Discrete Event Dynamic System), the JSP can be