【作者】 张超勇；

【导师】 李培根； 饶运清；

【作者基本信息】 华中科技大学 ， 机械电子工程， 2007， 博士

【摘要】 调度是影响制造业生产效率的关键因素。采用合理的调度可以缩短工期、减少库存、按时交货和提高信誉。随着全球市场竞争的加剧、客户需求的多样化和个性化,制造系统的调度问题日益受到广泛的重视。生产调度问题种类繁多,方法多样,其中单件车间调度(Job-Shop Scheduling Problem)是最基本、最著名的机器调度问题,同时也是最困难的NP-hard组合优化问题之一。人们为解决这一难题已经付出几十年的努力,但至今最先进的算法仍很难得到规模较小问题的最优解。近十几年来,通过模拟自然界中生物、物理过程和人类行为过程而发展的元启发式算法,如遗传算法、禁忌搜索、模拟退火、粒子群优化算法、蚁群优化算法等,为解决调度问题提供了新的思路和手段,引起了国内外学者广泛的兴趣。遗传算法和局部搜索算法是目前主要应用于调度的元启发式算法。遗传算法所具有的只根据个体的适应度值进行搜索、较少需要问题相关具体领域知识的特点使遗传算法在生产调度等问题中得到非常广泛的应用。本文改进传统的遗传算法,提出以下三点来解决Job-Shop问题:一是提出一种全主动调度类型,进一步缩小搜索的解空间;二是提出了一种基于工序编码的交叉算子POX(Precedence Operation Crossover),使子代能更好地继承父代的优良特征;三是为克服传统遗传算法存在的早熟收敛问题,设计了一种改进子代产生模式的遗传算法。用基准实例测试改进的遗传算法,试验结果显示该算法能比其他遗传算法更有效地解决调度问题。接着本文研究了局部搜索算法,特别是禁忌搜索算法,在Job-Shop调度问题中的运用。禁忌搜索算法的优化效率依赖于问题模型,邻域结构和移动评价策略是影响算法搜索效率和解质量的关键因素。本文提出一种新的高效邻域结构,结合适当的移动评价策略和禁忌搜索参数,设计了一种动态强化的禁忌算法。使用该算法对大量的基准实例进行测试,试验结果显示对于矩形基准实例,该算法在质量和效率上可以超越目前其他算法。最近的许多研究显示单一算法较难解决复杂的调度问题,混合优化算法能提供更强大的搜索能力。然而,到目前为止混合算法仍是一种艺术。调度问题的解空间结构属于非常复杂的“大山谷”(Big Valley)拓扑结构,为了更好地探索调度问题复杂的空间结构、弥补单一算法的不足,本文提出应用自然规律来混合算法,将不同算法进行有机和谐地结合,设计了两种混合优化算法,使算法更深刻地反映问题的本质。应用提出的混合优化算法求解著名Job-Shop调度基准问题,取得了迄今为止最好的结果,达到了国际水平的前沿。在ABZ、YN、SWV、TA和DMU基准问题的106个未解决实例中,改进了84个实例的当前最好解,有3个实例证明达到最优解。对于最著名的TA基准实例,发布的最好解已被作为最新结果在国外专业网站上公布。通过与已正式发表最好的算法进行比较可看出,对于极困难的Job-Shop调度问题,混合优化算法在解的质量方面超过目前最先进的算法。在实际生产环境中,调度问题具有多目标性、多资源性、动态性和随机性等特点。基于研究传统Job-Shop调度问题的成功经验,本文对实际生产中广泛存在的调度问题进行了深入研究,在性能指标方面,研究了总拖期时间最小、提前/拖期惩罚代价最小等性能指标;在生产模式方面,研究了柔性作业车间调度问题(Flexible Job-Shop Scheduling Problem)、动态调度(Dynamic Scheduling),并设计了相应的优化算法,如针对柔性作业车间调度问题的特点,提出了一种双层子代产生模式的改进遗传算法;将静态调度问题的成功经验扩展到动态调度问题,提出了一种基于改进遗传算法的滚动调度策略。基于这些研究成果开发出动态调度原型系统,使理论研究能应用于企业创造价值。作业车间调度是车间制造执行系统(MES)的核心功能之一,合理、有效的作业调度是MES在离散制造业成功应用的关键。在研究车间作业调度问题理论和应用的基础上,本文对单件小批量生产方式的车间作业计划与调度方面的实现方法进行了深入的研究,结合协作企业的应用背景,开发出敏捷化车间制造执行系统(AMES V1.0),并将AMES与其它的制造资源集成,创建了一个敏捷网络化制造系统集成平台。更多还原

【Abstract】 Scheduling is a key factor for manufacturing productivity. Proper and effective scheduling can help cut lead times, improve on-time delivery, reduce inventory, so as to increase the prestige of enterprises. Recently, with the upgrading of market competition as a result of the economic globalization and the variety and individuality of consumers’demands, scheduling is playing an increasingly important role in the manufacturing industry.Practically, different domains and applications require different variations of the scheduling problem. Meanwhile, the Job-Shop scheduling problem (JSP) is the most fundamental and well-known. The fact is that the JSP is notoriously difficult, as well as widely accepted as one of the most difficult NP-hard problems. Despite over 40 years of efforts, resulting in hundreds of published journal articles and tens of dissertations, even those state-of-the-art algorithms often fail to consistently locate optimal solutions to relatively small problem instances. During the last decade, the meta-heuristics algorithms developed by mimicking the process of natural laws, such as genetic algorithms (GA), tabu search (TS), simulated annealing (SA), particle swarm optimization (PSO), and ant colony optimization (ACO), have shown the effectiveness for the solution of difficult combinatorial optimization problems and captured the interest of a significant number of researchers.Among these approaches, genetic algorithm and local search are two primary algorithms applied to solving the JSP. Genetic algorithm, which exhibits parallelism, contains certain redundancy and historical information of past solutions, and requires little problem-specific knowledge other than fitness, has been widely applied in the production scheduling field. In this paper we improve the traditional GA and propose three novel features for this algorithm to solve the JSP. Firstly, a new full-active schedule (FAS) procedure based on the operation-based representation is presented to construct schedule, which further reduces the search space. Secondly, a new crossover operator, called Precedence Operation Crossover (POX), is proposed for the operation-based representation, which can preserve the meaningful characteristics of the previous generation. Thirdly, in order to reduce the disruptive effects of genetic operators, the approach of an improved generation alteration model is introduced. The proposed GA is tested on some standard instances and compared with the other GA procedures. The experimental results validate the effectiveness of the proposed algorithm. Next, the application of local search, especially tabu search, is studied.Tabu search is among the most effective approaches for solving the job shop scheduling problem. However, the efficiency of TS depends mostly on the modeling, and neighborhood structures and move evaluation strategies play the central role in the effectiveness and efficiency of TS for the JSP. In this paper, a new enhanced neighborhood structure is proposed. By combining it with the appropriate move evaluation strategy and parameters, we proposed a dynamic intensified TS approach. This approach is tested on a set of standard benchmark instances and found a large number of better upper bounds among the unsolved instances. The computational results show that for the rectangular problem our TS approach dominates all others in terms of both solution quality and performance.Genetic algorithm, simulated annealing and tabu search (local search techniques) are all naturally motivated and have complementary strengths and weaknesses. Recently, most studies indicate that a single technique cannot solve this stubborn problem, and hybrid methods are able to provide high-quality solutions within reasonable computing times. However, hybridizing algorithms are sort of an art so far. Since the solution space of the JSP owns“big valley”(BV) and the best elite solutions disperse over BV area. By application of the natural law to explore the whole big valley, two effective hybrid optimization strategies are proposed, which combine the advantage properties of each algorithm. The hybrid algorithms proposed were tested on the standard benchmark sets and compared with other approaches, we improved 84 upper bounds among the 106 unsolved instances for the general ABZ, YN, SWV, TA and DUM benchmark sets. Meanwhile, for the well-known Taillard’s benchmark set, I found 20 new upper bounds among the 33 unsolved instances, some of which provide the optimal solutions. In addition, the results of comparison between our hybrid algorithms and the best approximation algorithms show that for the most difficult Job-Shop scheduling problem our work has reached the advanced international level.Actually the scheduling problems in real world are complex, dynamic and require different sets of evaluation criteria. Based on the fruits of researching the traditional JSP, we studied the widely existed scheduling problems in practice, such as the flexible job-shop scheduling problem (FJSP), dynamic scheduling and their different sets of evaluation criteria, and proposed the corresponding optimal strategies according to their characteristics. For example, a multistage-based generation alteration model of genetic algorithm is proposed to solve the FJSP; an improved genetic-based rolling horizon scheduling strategy is presented, which extends the previous research on static scheduling to dynamic scheduling. In addition, the dynamic scheduling prototype system is developed, which can be adopted in enterprises to make contributions to the society.Scheduling is the key component of Manufacturing Execution System (MES). Proper scheduling is prerequisite for MES applied to manufacturing industry. Based on the study of theories and applications above, AMES (Agile Manufacturing Execution System, AMES V1.0) software has been designed and developed for the cooperative factory, and integrated with other manufacturing resources.更多还原