制造业的车间调度问题优化算法比较研究

摘要：目前，制造业的竞争日益激烈，在企业的日常运作过程中，会经常遇到各种各样的复杂的调度问题，车间生产调度问题解决的好坏直接影响着企业的运作效率和最终的客户满意程度，最终影响着企业对市场的反应能力和竞争力。因此，调度问题已经成为运营管理领域的一大研究热点。大量的学者研究生产调度优化问题，采用了各种优化方法。文章综述了车间生产调度问题的各种优化方法，对其发展历程、优缺点、适用性等都作了详细的说明，并对它们作以比较分析，从而找到最适合现实状况的优化方法。

关键词：调度问题；最优化算法；启发式算法

中图分类号：F273文献标识码：A

文章编号：1002-3100(2008)06-0117-03

Abstract: At present, competition in manufacturing is growing tougher and tougher. There are all kinds of complicated scheduling problem in operations of manufacturing companies. How to solve the scheduling problem will affect the efficiency and the customer"s satisfaction, and the power and response ability of the company. So scheduling problem becomes a very popular problem in OM. Lots of scholars adopts various methods to solve actual problem. This paper sums up all kinds of methods of scheduling problem and particularly explain merit and disadvantages, evolution course and applicability, which compare and analyze them each other in order to discover best of realistic status"s optimum methods.

Key words: scheduling problem; optimized algorithm; heuristic algorithm

0引言

制造业是我国国民经济的支柱产业，是直接创造社会财富的基础。随着人们生活水平的日益提高、科技创新速度的加快和市场的国际化，制造业市场环境发生了巨大变化，需求日益个性化、多样化和快速变化。这使得倡导标准化和批量化的大批量制造模式陷入了前所未有的困境。按顾客订单生产的多品种、小批量，以及大规模定制的生产模式逐渐成为制造行业的主流。这种情况下，生产线同时加工的产品种类增加，给生产作业计划调度增加了难度，同时也使优化生产作业计划提高生产效率成为制造业管理技术革新的重要内容。

目前，制造业产品竞争的焦点在于产品质优价廉、准时交货、多品种小批量，而生产车间作业的调度是制造企业运营管理所面临的基本问题，在企业的日常运作过程中，会经常遇到各种各样的调度问题，调度问题解决的好坏直接影响着企业的运作效率和最终的客户满意程度，最终影响着企业对市场的反应能力和竞争力。

1问题描述

车间调度问题一般可以描述为：n个工件在m台机器上加工，一个工件分为k道工序，每道工序可以在若干台机器上加工。每一台机器在每个时刻只能加工某个工件的某道工序，只能在上道工序加工完成后才能开始下一道工序的加工，前者称为占用约束，后者称为顺序约束。车间调度问题的决策内容包括分配决策（工件的加工顺序）、时间决策（工件各工序的加工时间）和路径决策（工件工序的加工设备的分配）。所以车间调度的实质是属于NP-Hard（Nondeterministic polynomial-Hard, 非确定性多项式难问题）组合问题。随着问题规模的扩大，组合优化问题的搜索空间急剧扩大，有时在目前的计算机上用枚举法很难或者甚至不可能得到其精确最优解。对于这类复杂问题，人们已意识到应把精力放在寻求其满意解上。

2车间调度问题的优化方法

自从上世纪50年代以来，调度问题在学术界得到了广泛的研究。五十多年来，出现了大量的理论研究。这些研究基本上都致力于寻找各种各样调度问题的多项式算法。但是，很多的调度问题是不存在多项式算法的，在此过程研究中，导致了计算复杂性概念的诞生。此后，调度问题的理论研究变为或者寻找到问题的多项式算法或者证明该问题不存在多项式算法。

在对经典的调度问题取得大量的理论成果之后，90年代开始，理论研究的重心转移到将这些经典的算法更多的与实际的调度问题结合上，学术界转向了对复杂调度问题的启发式算法和搜索技术的研究。这些近似算法能够在一个相对合理的时间内找到一个满意的调度方案。

下面，简单介绍在制造业应用的车间调度优化算法。这些方法可分为最优化算法和启发式算法两类。

2.1最优化算法

优化算法又分为有效最优化方法和精确最优化方法。有效最优化方法是指在多项式时间内求得最优化调度的一类方法。但是，由于多数调度问题的NP-Hard特性，这类有效最优化算法是不存在的。精确最优化算法是一类具有一般性的组合最优化方法，主要包括线性规划LP、非线性规划NLP、动态规划DP、拉格朗日乘子法和分枝定界等。LP 作为一种精确的运筹学方法，是较成熟的方法之一，但实际中很多问题不能以简单的线性关系精确表达，且涉及的变量多为整数，因此限制了LP的使用。分枝定界的使用效率与定界的方法及搜索空间的结构密切相关，仅适用于中小规模的问题，在解决受多重复杂条件约束和含有不确定因素的排序问题时结果不理想。

2.2启发式算法

调度算法的研究经历了从有效最优化算法、精确求解算法到计算复杂性的研究、启发式算法及其有效性的研究历程。进入80年代，随着技术和管理对更高层次的要求，过多的假设和对制造过程的简化在很大程度上制约着调度理论的研究和实际应用的范围，于是开展了对更复杂、更接近于实际的调度目标函数、制造环境及工艺约束条件的问题的研究。由此产生的启发式算法有：

2.2.1优先分派规则。一个调度规则可以由多个优先级规则和（或）启发式规则组成。优先级规则（Priority Rule）按某种方法给每个待排序的工作指定一个数值，并优先安排具有最小值的工作。常用的规则有最早交货期（Earliest due-date，EDD）、最短加工时间（Shortest processing time，SPT）、最长加工时间（Largest processing time，LPT）、先入先出（First in first out，FIFO）等，实际使用时可以将若干个优先级规则加权组合，形成组合的优先级规则。启发式规则指经验法则，是比优先级规则更深一层的一些规则，其优点是可以缩短寻优过程。

2.2.2基于知识的方法。基于知识的调度优化方法利用专家系统自动产生调度或辅助人去调度，它将传统的调度方法与基于知识的评价相结合，对设计适用于生产实际的高效益、高柔性的系统具有启发意义。在应用中，专家系统中知识的获取和推理速度是两个瓶颈，专家系统有研制花费昂贵、知识的难于获取和表达的缺点，将人工智能方法能与其他方法结合会得到更有效的调度方案。

Farhoodi在1990年提出了一个针对动态的车间调度问题的基于知识的优化方法，是基于知识的方法在调度问题中的很好的应用[1]。

2.2.3神经网络方法。神经网络已被成功地应用于解决组合优化问题，用神经网络的方法建立生产调度的模型关键在于分别用不同类型的单元网络表示不同类型的约束条件，然后通过适当连接这些单元神经网络，得到资源约束和排序约束的网络表示，进一步实现生产调度的建模。在大规模、复杂调度问题中，存在计算速度慢与结构参数难于确定的缺点，易陷入局部最小和全局搜索能力弱。王万良在2002年提出了基于神经网络的作业车间生产调度的新方法，给出了作业车间生产调度问题（JSP）的约束条件及其换位矩阵表示，提出了新的包括所有约束条件的计算能量函数表达式，得到相应的作业车间调度问题的Hopfield神经网络结构与权值解析表达式，并提出相应的Hopfield神经网络作业车间调度方法[2]。

2.2.4模拟退火算法。模拟退火算法由Metropolis等人提出，利用受控随机概率接受劣解，避免陷入局部最优，是一种串行全局优化算法，在运筹学的各个领域有大量的研究。其收敛性要求初温应足够高，使解空间各状态能以几乎相同的概率出现，模拟退火的弱点是搜索空间过于庞大和下降温度难于掌握。赵良辉2006年结合车间调度问题的特点阐述了模拟退火算法在解决车间调度问题上的应用，提出了基于模拟退火算法的车间调度问题模型，并以Matlab为工具进行了仿真实验[3]。

2.2.5遗传算法。遗传算法是Holland基于自然遗传进化的绝对模型提出的并行搜索机制，算法简单，鲁棒性强，非常适合解决调度问题。对生产调度问题，基因的选取一般为排序决策变量，通常采取二进制的编码方式，同时交叉算子和编码表示对算法的收敛性会产生影响。应用中，为解决收敛速度慢的缺点，许多学者尝试采取遗传算法和其他算法相结合的方式。此外，遗传算法对初始种群很敏感，有采取其他启发式（如优先排序规则）产生初始种群的改进方法，近年来，对基于遗传算法的混合优化策略方面的研究出现了一些成果。

Crauwels(1996)研究了一个单机器的批处理生产调度问题，通过数值仿真计算，比较了模拟退火、禁忌搜索、遗传算法和一种启发式算法，结果表明在该环境下遗传算法效果最好[4]。

2.2.6禁忌搜索算法。禁忌搜索是Glove提出的模拟智能过程的一种具有记忆功能的全局逐步优化算法，对变动的排序在其可行解的所有空间中进行搜寻。通过设置禁忌表记忆近期搜索路径，避免陷入局部最优或重复过去的搜索，并由此控制进一步的搜索方向，同时利用中、长期的存储机制进行强化和多样化搜索。黄志在2006年描述了一种解决作业车间调度最短完工时间问题的有效的启发式算法，该算法基于禁忌搜索技术。为了得到更好的结果，还将倒转技术引入到算法中。从对一组问题基准实例的实验计算结果看，该算法在合理的计算时间内对多个实例得到比2004年提出的ISSB算法更好的结果[5]。

2.2.7拍卖算法。拍卖算法（bidding algorithm）是研究调度问题的一种新思路，也称为基于市场的（market based）排序或基于代理的（agent-based）排序。该方法需要设立工件代理（job agent）和机器代理（machine agent），并建立一套市场拍卖机制，通过市场招投标的方式，确定工件的加工顺序。工件代理的目标是在预算约束条件下，使工件被按时完成；机器代理的目标是利益最大化。应用该方法调度的研究内容包括拍卖机制的建立、定价的规则、预算约束的建立、两类代理的最优决策法则等。

Ouelhadj（2004）研究了钢铁生产中的连铸和热轧的生产过程，分析了一种基于代理的调度机制，设计了基于合同网络协议的两层投标机制，并将禁忌搜索算法包含在调度机制中，最后通过算例分析了该方法的效果[6]。

2.3各种算法的比较分析

最优化算法的优点在于求解精确，目标直指最优解，在面对简单问题的时候，可以找到适合问题的最优解。但是，当问题的规模增大时，算法的计算时间随之呈指数增加，会发生“组合爆炸”，给求解计算带来困难。另外，使用最优化算法时，通常要加上一些脱离实际情况的假设，在一定程度上也导致了理论研究与实际应用的脱节。

与精确最优化算法相比，启发式算法的明显优势在于：启发式算法相对比较简单，计算效率高，能显著地节省计算开支；而且启发式算法灵活多变，在考虑多种方案和不能用定量表示约束集合时，常能把它作为制定计划的工具。但是，启发式算法有明显不足之处，即有可能出现所产生的解比全局最优解差很多的情况，而且差的程度总是不够明确。因此，合理的计算时间和所求出的解的最优性就成为衡量启发式算法性能的标准。

那么对于启发式算法中的各种算法来说，在一定时期、一定情况下都有各自的优点，都有解决某一类问题的优越性，但随着发展的需要，对优化方法要求也越来越高，下面对各种方法进行比较分析，通过表格的形式来展现各自的特点。

纵上所述，车间作业调度问题中的各种算法各有利弊，在不同情况下可以有针对性的选择。

3结论

本文是针对制造业实际应用当中的车间调度问题而言的，对不同条件下的调度问题应该有针对性的选择不同的方法。将各种优化方法都详细地作了介绍，给出其优缺点及适用性，让读者清晰明了，可以根据各自所需进行合理的选择。

另外从目前的研究情况来看，针对实际生产中的复杂问题，越来越多的迹象表明在同一个问题中使用两个或多个算法结合的方法更容易得到更好的结果，所以混合算法的使用是将来的一个发展趋势。

参考文献：

[1]Farhoodi F A. Knowledge-based approach to dynamic job-shop scheduling[J]. International Journal of Computer Integrated Manufacturing, 1990,3(2):84-95.

[2] 王万良，吴启迪，徐新黎. 基于Hopfield神经网络的作业车间生产调度方法[J]. 自动化学报，2002,28(5):838-844.

[3] 赵良辉，邓飞其. 用于作业车间调度的模拟退火算法[J]. 制造业自动化，2006,28(3):10-23.

[4]H.A.J. Crauwels, C.N. Potts, L.N. Van Wassenhove. Local search heuristics for single-machine scheduling with batching to minimize the number of late jobs[J]. European Journal of Operational Research, 1996(90):200-213.

[5] 黄志，黄文奇. 一种基于禁忌搜索的作业车间调度算法[J]. 计算机工程与应用，2006(3):12-14.

[6]D. Ouelhadj, S. Petrovic, P.I. Cowling and A. Meisels. Inter-agent cooperation and communication for agent-based robust dynamic scheduling in steel production[J]. Advanced Engineering Informatics, 2004(18):161-172.

推荐访问:调度 算法 车间 制造业 优化