任务6.1　柔性作业车间调度分析与建模

任务6.1　柔性 作业车间调度分析与建模

20世纪90年代以来，我国制造业持续高速发展，成为拉动国民经济发展的主要力量。全球性竞争的加剧，给国内的制造业带来了新的挑战。企业要想在激烈的竞争中立于不败之地，就必须以最低的成本、最好的质量、最快的速度和最优的服务来响应市场。由于市场竞争的日益激烈，以及客户需求的个性化和多样化，多品种、中小批量生产方式已经被大多数企业所接受。在这种“离散”的生产方式下，产品生产规模小、品种多，造成生产作业过程的信息复杂且不易控制，均衡的生产计划和作业计划难以实现，容易导致不能按期交货、质量得不到保证、经济效益降低等问题。由此调度优化问题应运而生。调度优化问题是指“如何把有限的资源在合理的时间内分配给若干个任务，以满足、优化一个或多个目标”。调度优化问题几乎存在于各个领域，如企业管理、交通运输、航空航天、医疗卫生、能源动力和网络通信等。由此可见，调度优化问题的研究在现实中有重大意义。

1.任务引入

为了提高制造业的竞争能力，适应国际上的先进制造模式，制造企业开始逐渐引进和开发了产品研发和管理的信息化软件，例如，计算机辅助设计（Computer Aided Design，CAD）、计算机辅助工程分析（Computer Aided Engineering，CAE）、计算机辅助工艺规划（Computer Aided Process Planning，CAPP）、计算机辅助制造（Computer Aided Manufacturing，CAM）、产品数据管理（Product Data Manage ment，PDM）、制造资源计划（Manufacture Resource Planning，MRP）等软件。随着以上软件应用的深入，制造企业希望能够将上述软件的信息进行集成，以便对产品从投料到成品的制造全过程进行控制，从而达到使生产制造活动更加高效、敏捷、柔性化的目的。为此我国又逐渐引入和开发了制造执行系统（Manufacturing Execution System，MES）、计算机辅助质量管理（Computer Aided Quality，CAQ）、计算机辅助检测（Computer Aided Testing，CAT）、企业资源规划（Enterprise Resource Planning，ERP）等软件。制造执行系统能根据所采集的车间底层与生产相关的实时数据信息，以及MRP、ERP、PDM等软件生成的产品生产的长期计划，对短期生产作业计划进行调度、资源配置和生产过程等系统优化。制造执行系统正逐渐在制造企业得到广泛的应用，使制造企业朝制造柔性化和管理精细化的方向发展，从而提高响应市场变化的实时性和灵活性，提高生产线的运行效率，降低不良品率，降低生产成本。其中车间调度是制造执行系统的核心功能之一，是其在制造企业成功应用的关键。

2.任务目标

1）知识目标

（1）了解车间调度问题的描述、分类及特性。

（2）理解柔性作业车间调度问题描述。

2）技能目标

能够通过柔性作业车间调度问题的研究方法进行优化设计。

3）素养目标

培养学生整理、归纳、总结的能力，增强学生的自信心。

3.任务分析

车间调度技术是实现制造企业生产高效率、高柔性和高可靠性的关键技术之一。传统车间调度模式是：假设工序加工所需要的资源是不具备柔性的资源，工件的所有工序的加工机器是唯一的，且加工顺序是已知的，调度时，通过确定工序在每台加工机器上的加工顺序来优化完工时间等系统目标。一般研究车间调度问题时，都会以传统作业车间调度问题（Jobshop Scheduling Problem，JSP）为基础进行研究，每个工件的每道工序只能在一台机器上加工，并且只能加工一次，加工时间是确定的。

随着大批量连续生产方式逐渐被适应市场动态变化的多品种、小批量离散生产方式所替代，一个制造企业的生存能力和竞争能力在很大程度上取决于它是否能在较短的生产周期内生产出较低成本、较高质量的多个的品种产品。随着柔性制造系统（Flexible Manufacture System，FMS）和数控加工中心（Computer Numerical Control，CNC）等带有一定柔性的生产系统的出现，以往经典作业车间调度的研究成果不能非常快速地直接应用于新的制造模式，于是柔性作业车间调度问题（Flexible Job-shop Scheduling Problem，FJSP）也就成为研究重点，它是传统作业车间调试问题的扩展。工件的每道工序可以在多台相同或不同的机器上进行加工，加工时间不一定相同，在实际生产中可以按照资源负荷情况，灵活地进行资源的选择，以提高加工的灵活性。

4.相关知识

1）加工的优点

第一，可以提高设备的利用率。机器一旦空闲就可以安排工件进行加工，减少设备闲置和等待的时间。

第二，具有维持生产稳定的能力。当一台或多台机器发生故障时，工件可以绕过故障机器，在其他机器上进行加工，生产得以继续，从而保证生产稳定。

第三，可以提高产品质量和缩短生产周期。与经典的JSP模型相比，同一工件的多个工序可以在同一台机器上连续进行加工，减少了中间装卸和搬运等造成时间的消耗。

虽然传统作业车间调度问题在理论上取得了重大进展，然而实际制造系统中的车间调度问题不仅在问题模型上比传统作业车间调度问题复杂，而且具有计算复杂、多目标、不确定性、动态性等特点。具体表现如下。

（1）计算复杂。

柔性作业车间调度问题是传统作业车间调度问题的扩展，它不仅需要确定工序加工的顺序，还要给每道工序分配机器，是比传统作业车间调度问题更为复杂的NP-hard问题。

（2）多目标。

在实际生产中经常需要考虑多项性能指标要求，且各项性能指标要求可能彼此冲突。常用的调度性能指标包括：最大完工时间、交货期、机器总负荷、生产成本、延迟或拖期、库存等。

（3）不确定性。

在实际生产中存在广泛的不确定性因素，如机器故障、操作人员不熟练、原材料性质存在差异、刀具磨损等，很少能获得确定的加工信息。

（4）动态性。

实际生产过程是一个动态的过程，加工工件通常是依次进入待加工状态的，各种工件不断进入制造系统接受加工，已加工完的工件又不断地离开制造系统。(https://www.daowen.com)

目前车间静态、不确定随机、动态调度范围的定义存在多种不同的分类模型，而这些模型直接影响解决问题的复杂性，因此要求模型简单，接近实际生产过程。简单、实用的调度分类模型包括静态调度、动态调度、多目标调度、不确定调度、多目标不确定调度。

因此，这里将调度研究延伸为更具实际意义的问题，对柔性作业车间调度这一类型的调度问题进行深入研究，这在理论上和实际生产上都具有广泛的实用性和重要的意义。

从理论方面来讲，理论应用于实际能否成功，在于建立的模型和研究的问题是否符合当前实际的生产状况，同时也在于对所建立的问题模型是否存在有效的求解方法。柔性作业车间调度问题的研究，突破了制造企业传统生产中工件加工路线固定的限制，是非常复杂的组合优化问题，因此，从理论上对柔性作业车间调度问题进行研究，对于发展优化技术和解决包括调度问题在内的组合优化问题都具有重大的意义。

从实际生产方面来讲，柔性作业车间调度问题在实际生产中具有实际应用价值。这里由单目标柔性作业车间调度问题开始研究，逐渐深入，直至对多目标和不确定环境下的柔性作业车间调度问题进行研究，减少实际生产中设备的闲置和等待时间，提高设备利用率，使各道工序之间的衔接更加连续、紧凑。

由于现实应用中会遇到更加复杂的调度问题，所以进一步丰富车间调度理论成果并将其应用于实际生产调度问题或缩小理论成果与实际问题的差距，将会产生巨大的经济效益和实践价值。

2）车间调度问题的描述、分类及特点

（1）车间调度问题的描述。

调度问题的一般性定义为：在一定的约束条件下，把有限的资源在时间上分配给若干个任务，以满足或优化一个或多个性能指标。

从这个定义可见，调度不仅要将任务排序，还要确定各个任务的开工和结束时间。因为在多个任务的开工时间之间可以插入无限的空闲时间。通常假定每个任务都按照其最早可开工时间开始加工，那么任务的一个排序就可以确定一个调度方案。

在制造业中，车间调度问题可以描述为：n个工件在m台机器上加工；一个工件有多道工序，每道工序可以在若干台机器上加工，并且必须按一些可行的工艺次序进行加工；每台机器可以加工工件的若干工序，并且在不同的机器上加工的工序集可以不同。车间调度的目标是将工件合理地安排到各机器，并合理地安排工件的加工次序和开工时间，使约束条件被满足，同时优化一些性能指标。在实际制造系统中，还要考虑刀具、托盘和物料搬运系统的调度问题。

（2）车间调度问题的分类。

车间调度问题的分类方法较多，根据工件和车间构成的不同，车间调度问题可分为以下几种。

①单机调度问题。

在单机调度问题（Single Machine Scheduling Problem，SMP）中，加工系统只有一台机器，待加工的工件有且仅有一道工序，所有工件都在该机器上进行加工。此问题是最简单的车间调度问题。

②并行机调度问题。

在并行机调度问题（Parallel Machine Scheduling Problem，PMP）中，加工系统中有多个完全相同的机器，每个工件只有一道工序，工件可以在任意一台机器上进行加工。

③开放车间调度问题。

在开放车间调度问题（Open Shop Scheduling Problem，OSP）中，每个工件的工序的加工顺序是任意的。工件的加工可以从任何一道工序开始，在任何一道工序结束。工件的加工没有特定的技术路线约束，各个工序之间没有先后关系约束。

④流水车间调度问题。

在流水车间调度问题（Flow Shop Scheduling Problem，FSP）中，加工系统有一组功能不同的机器，待加工的工件包含多道工序，每道工序在一台机器上加工，所有工件的加工路线都是相同的。每个工件工序之间有先后顺序约束。

⑤作业车间调度问题。

在作业车间调度问题（Job Shop Scheduling Problem，JSP）中，加工系统有一组功能不同的机器，待加工的工件包含多道工序，每道工序在一台机器上加工，工件的加工路线互不相同，每个工件工序之间有先后顺序约束。

（3）车间调度问题的特点。

车间调度问题具有以下特点。

①多约束性。

在通常情况下，工件的加工路线是已知的，并且受到严格的工艺约束，各道工序在加工顺序上具有先后约束关系；同时，工件的加工机器集是已知的，工件必须按照工序顺序在可以选择的机器上进行加工。

②离散性。

车间生产系统是典型的离散系统，其调度问题是离散优化问题。工件的开工时间、任务的到达、订单的变更，以及设备的增添或故障等都是离散事件。可以利用数学规划、离散系统建模与仿真、排序理论等方法对车间调度问题进行研究。

③计算复杂性。

车间调度问题是一个在若干等式和不等式约束下的组合优化问题，从计算时间复杂度看是一个NP-hard问题。随着调度规模的扩大，问题可行解的数量呈指数级增加。很简单的例子如：在工件和机器的数量均为10的单机调度问题中，当单纯考虑加工周期最短时，可能的组合数就已达到（10！）10。

④不确定性。

在实际车间调度中有很多随机因素，如工件到达时间具有不确定性，工件的加工时间随着不同的加工机器也有一定的不确定性。而且，系统中常有突发事件，如紧急订单插入，订单取消、原材料紧缺、交货期变更、设备发生故障等。

⑤多目标性。

在不同类型的制造企业和不同的生产环境下，调度目标往往形式多样、种类繁多，如完工时间最短、交货期最早、设备利用率最高、成本最低、在制品库存量最少等。多目标性有两层含义，一是目标的多样性；二是多个目标需要同时得到满足，并且各个目标往往是相互冲突的。

车间调度问题的特性，使车间调度问题从产生到现在，一直吸引着来自不同领域的研究人员寻求不同的有效方法对其求解。但是，多年来的研究仍不能完全满足实际应用的需要，促使人们更加深入、全面地对其进行研究，提出更有效的理论和方法，来满足制造企业的实际需求。

5.任务准备

下面介绍柔性作业车间调度问题的研究方法。

柔性作业车间调度问题一直是极其困难的组合优化问题，其研究方法也随着调度模型的变迁从开始的数学方法发展到目前启发式的智能算法。目前解决柔性作业车间调度问题的方法主要分为两类：精确方法（exact method）和近似方法（approximation method）。精确方法也可称为最优化方法，能够保证得到全局最优解，但只能解决较小规模的问题，而且速度很慢。近似方法可以很快地得到问题的解，但不能保证得到的解是最优的，不过对于大规模问题是非常合适的，可以较好地满足实际问题的需求。

1）精确方法

精确方法主要包括整数规划方法、混合整数规划方法、拉格朗日松弛法、分解方法、分支定界法等。

（1）数学规划方法。

数学规划方法中最常见方法是混合整数规划。混合整数规划有一组线性约束和一个线性目标函数，该方法限制决策变量都必须是整数。这导致在运算中出现的整数个数以指数规模增长，即便使用更好、更简洁的公式表述，也需要大量的约束条件。

较多成功的数学模型的建立都归功于拉格朗日松弛法和分解方法。拉格朗日松弛法用非负拉格朗日乘子对工艺约束和资源约束进行松弛，最后将惩罚函数加入目标函数。上海交通大学的刘学英用拉格朗日松弛法解决车间调度问题。分解方法将原问题分解为多个小的易于解决的子问题，然后对子问题寻找最优解。

（2）分支定界法。

分支定界法用动态树结构来描述所有的可行解排序的解空间，树干的分支隐含要被搜索的可行解。分支定界法非常适合解决总工序数小于250的柔性作业车间调度问题，对于大规模的柔性作业车间调度问题，它需要很多计算时间，这限制了它的使用。目前，对这种方法研究的重心是如何与智能算法结合，减少最初的搜索阶段中的节点，提高搜索效率和完善求解效果。

2）近似方法

由于大多数柔性作业车间调度问题的复杂性和所存在的上述问题，近似方法成了一种可行的选择。近似方法可以在较为合理的时间内迅速求得可以令人接受的满意解。由于它的求解速度快，解的质量还可接受，所以它可用于解决较大规模的柔性作业车间调度问题。

3）人工智能方法

在20世纪80年代出现的人工智能方法在柔性作业车间调度问题研究中占据重要的地位，也为解决柔性作业车间调度问题提供了一种较好的途径。它主要包括：约束满足，神经网络，专家系统，多智能体技术，以及后来人们通过模拟或揭示某些自然现象、过程和规律而发展的进化算法（如遗传算法、免疫算法、蚁群优化算法和粒子群优化算法等）。

（1）约束满足。

约束满足（Constraint Satisfaction，CS）是指通过运用约束来减小搜索空间的有效规模的方法。这些约束限制了选择变量的次序和分配到每个变量可能值的排序，在一个值被分配给一个变量后，不一致的情况被剔除。去掉不一致情况的过程称为一致性检查（consistency checking），但是这需要进行回访修正。当所有的变量都得到分配的值，并且不与约束条件冲突时，约束满足问题就得到了解决。

（2）神经网络。

神经网络（Neural Networks，NN）通过一个Lyaplmov能量函数来构造其极值，当神经网络迭代收敛时，能量函数达到极小，使与能量函数对应的目标函数得到优化。用神经网络解决旅行商问题（TSP）是其在组合优化问题中最成功的应用之一。目前，神经网络仅能解决规模较小的柔性作业车间调度问题，而且计算效率非常低，以至于不能较好地用于求解实际大规模的柔性作业车间调度问题。

（3）专家系统。

专家系统（Expert System，ES）是指一种能够在特定领域内模拟人类专家思维来解决复杂问题的计算机程序。专家系统通常由人机交互界面、知识库、推理机、解释器、综合数据库和知识获取6个部分构成。它将传统的调度方法与基于知识的调度评价相结合，根据给定的优化目标和系统当前状态，对知识库进行有效的启发式搜索和并行模糊推理，避开烦琐的计算，选择最优的调度方案，为在线决策提供支持。比较著名的专家系统有ISIS、OPIS、CORTES、SOJA等。专家系统需要丰富的调度经验和大量知识的积累，这使其开发周期较长、成本较高、对新环境的适应能力较差，因此专家系统一般对应用领域的要求非常严格。

（4）多智能体技术。

为了解决复杂问题，克服单一的专家系统所造成的知识有限、处理能力弱等问题，人们提出了分布式人工智能（Distributed Artificial Intelligence，DAI）。多个智能体的协作正好符合分布式人工智能的要求，因此出现了多智能体系统（Multi-Agent-System，MAS）。由于多智能体系统对开放和动态的实际生产环境具有良好的灵活性和适应性，所以它在实际生产中有较多不确定因素的车间调度领域中获得越来越广泛的应用。不过，多智能体系统和专家系统具有相同的不足，也需要丰富的调度经验和大量知识的积累等。

（5）进化算法。

进化算法（Evolutionary Algorithm，EA）通常包括遗传算法（Genetic Algorithm，GA）、遗传规划（Genetic Programming，GP）、进化策略（Evolution Strategies，ES）和进化规划（Evolutionary Programming，EP）。它们都是模仿生物遗传和自然选择的机理，用人工方式构造的一类优化搜索算法。它们的侧重点不一样，遗传算法主要发展自适应系统，是应用最广的算法；进化规划主要求解预期问题；进化策略主要解决参数优化问题。

（6）蚁群优化算法。

蚁群优化算法（Ant Colony Optimization，ACO）模拟蚂蚁在寻找食物的过程中发现路径的行为。蚂蚁在寻找食物的过程中，会在它们经过的地方留下一些化学物质“外激素”（stigmergy）或“信息素”（phero-mone），这些物质能被同一蚁群中后来的蚂蚁感受到，并作为一种信号影响后来者的行动，而后来者也会留下外激素对原有的外激素进行修正，如此反复循环下去，在外激素最强的地方形成一条路径。蚁群优化算法在求解复杂组合优化问题方面有一定的优越性，不过容易出现停滞现象，收敛速度慢。

（7）粒子群优化算法。

粒子群优化（Particle Swarm Optimization，PSO）算法源于对鸟群捕食行为的模拟研究。在粒子群优化算法中，系统初始化为一组随机解，称为粒子。每个粒子都有一个适应值表示粒子的位置，还有一个速度来决定粒子飞行的方向和距离。在每一次迭代中，粒子通过两个极值来更新自己：一个极值是粒子自身所找到的最优解，称为个体极值；另一个极值是整个种群目前找到的最优解，称为全局极值。我国对粒子群优化算法在柔性作业车间调度问题中的应用研究较多。

4）局部搜索算法

局部搜索（Local Search，LS）算法是人们从生物进化、物理过程中受到启发而用于求解组合优化问题的方法，是从早期的启发式算法变化而来的。它以模拟退火算法、禁忌搜索算法为代表，应用广泛。局部搜索算法必须依据问题设计优良的邻域结构，产生较好的邻域解来提高算法的搜索效率和能力。

（1）模拟退火算法。

模拟退火（Simulated Annealing，SA）算法源于模拟退火的过程并且结合Metropolis准则。模拟退火算法在进行局部搜索过程中，某个解的目标函数值即使变坏，也仍可以采用Metropolis准则以一定的概率接受新的较差解或继续在当前邻域内搜索，以免陷入局部最优解。整个过程由温度参数t来控制。由于模拟退火算法是一般的随机搜索算法，搜索过程没有记忆功能，所以在求解柔性作业车间调度问题时不能非常迅速地得到较好解。不过，模拟退火算法与其他算法相结合可以增强局部搜索能力，可以在结果和计算时间上都有明显改善。

（2）禁忌搜索算法。

禁忌搜索（Tabu Search，TS）算法在运行时，按照某种方式产生一个初始解，然后搜索其邻域内的所有可行解，取其最优解作为当前解。为了避免重复搜索，它引入了灵活的存储结构和相应的禁忌准则（即禁忌表和禁忌对象）；为了避免陷入局部最优解，它引入了特赦准则，允许一定程度地接受较差解。禁忌搜索算法的求解速度快而且应用较为广泛，然而它依赖于问题模型和邻域结构等，可以与其他算法结合来提高局部搜索能力。

除了上述方法以外，还有很多种方法可用来对柔性作业车间调度问题进行求解，如Petri网和仿真调度法、文化算法（cultural algorithm）、DNA算法、Memetic算法、分散搜索（scatter search）算法等。每一种算法都有一定的优势，也存在一定的缺点，如何将它们取长补短地混合在一起进行使用是当前及未来研究的热点。

6.任务实施

1）柔性作业车间调度问题的描述与分类

柔性作业车间调度问题的描述如下。n个工件（J1，J2，…，Jn）要在m台机器（M1，M2，…，Mm）上加工；每个工件包含一道或多道工序；工序顺序是预先确定的；每道工序可以在多台不同机器上进行加工；工序的加工时间随机器的不同而不同；调度目标是为每道工序选择最合适的机器，确定每台机器上各道工序的最佳加工顺序及开工时间，使整个系统的某些性能指标达到最优。因此，柔性作业车间调度问题包含两个子问题：确定各工件的机器（机器选择子问题）和确定各个机器上的加工顺序（工序排序子问题）。

此外，在加工过程中还需要满足下面的约束条件。

（1）同一台机器在某一时刻只能加工一个工件。

（2）同一工件的同一道工序在同一时刻只能被一台机器加工。

（3）每个工件的每道工序一旦开始，加工便不能中断。

（4）不同工件具有相同的优先级。

（5）不同工件的工序没有顺序约束，同一工件的工序有顺序约束。

（6）所有工件在零时刻都可以被加工。

柔性作业车间调度问题根据资源选择限制条件和柔性程度，可以分为完全柔性作业车间调度问题（Total FJSP，T-FJSP）和部分柔性作业车间调度问题（Partial FJSP，P-FJSP）。在T-FJSP中，所有工件的每一道工序都可以在可选择的机器中选择任何一台机器进行加工；在P-FJSP中，至少存在一道工序的机器只能是可选择的机器中的部分机器，即机器集的真子集。也可以说，T-FJSP只是P-FJSP的一个特例。P-FJSP更加符合实际生产系统中的调度问题，研究P-FJSP比研究T-FJSP更具有实际意义，P-FJSP比T-FJSP更加复杂。

在柔性作业车间调度问题中，还存在循环排列的特性（circular permutation）与传统车间调度问题不同的问题，即在柔性作业车间调度问题中，存在同一个工件的多道工序可以被同一台机器进行加工，而不是每一道工序只能被同一台机器加工一次。这也增加了求解柔性作业车间调度问题的难度。传统车间调度问题的解空间巨大，包含（n！）m种排列，已经证明是NP-hard问题。柔性作业车间调度问题的解空间更是巨大，包含mn×（n！）m种排列，其计算复杂性可想而知。

2）柔性作业车间调度问题的数学模型

定义以下符号。

n：工件总数。

m：机器总数。

Ω：总的机器集。

i，e：机器序号，i，e=1，2，3，…，m。

j，k：工件序号，j，k=1，2，3，…，n。

hj：第j个工件的工序总数。

l：工序序号，l=1，2，3，…，hj。

Ωjh：第j个工件的第h道工序的可选机器集。

mjh：第j个工件的第h道工序的可选机器数。

Ojh：第j个工件的第h道工序。

Mijh：第j个工件的第h道工序在机器i上加工。

pijh：第j个工件的第h道工序在机器i上的加工时间。

sjh：第j个工件的第h道工序的开工始时间。

cjh：第j个工件的第h道工序的加工完成时间。

L：一个足够大的正数。

dj：第j个工件的交货期。

Cj：每个工件的完成时间。

Cmax：最大完工时间。

，所有工件工序总数。

一般柔性作业车间调度问题受到下列约束。

式中：i=1，2，3，…，m；j=1，2，3，…，n；h=1，2，3，…，hj。

式中：j=1，2，3，…，n；h=1，2，3，…，hj-1。

式中：j=1，2，3，…，n。

式中：j=0，1，2，…，n；k=1，2，3，…，n；h=1，2，3，…，hj；l=1，2，3，…，hk；i=1，2，3…，m。

式中：j=1，2，3，…，n；k=0，1，2，…，n；h=1，2，3，…，hj-1；l=1，2，3，…，hk；i=1，2，3，…，m

式中：h=1，2，3，…，hj；j=1，2，3，…，n。

式中：i=1，2，3，…，m；k=1，2，3，…，n；l=1，2，3，…，hk。

式中：i=1，2，3，…，m；j=1，2，3，…，n；h=1，2，3，…，hk

式中：j=0，1，2，…，n；h=1，2，…，hj。

式（6-1）和式（6-2）表示每一个工件的工序顺序约束；式（6-3）表示工件的完工时间的约束，即每一个工件的完工时间不可能超过总的完工时间；式（6-4）和式（6-5）表示同一时刻同一台机器只能加工一道工序；式（6-6）表示机器约束，即同一时刻同一道工序能且仅能被一台机器加工；式（6-7）和式（6-8）表示每一台机器存在循环操作；式（6-9）表示各个参数变量必须是正数。

3）柔性作业车间调度问题的析取图模型

在柔性作业车间调度问题中，存在循环排列的特性，即同一个工件的多道工序可以在同一台机器上连续或间隔加工。当柔性作业车间调度问题中每道工序确定了加工机器之后，即转变为一般的车间调度问题。析取图（disjunctive graph）模型是描述车间调度问题的一种重要形式。析取图模型G=（N，A，E），其定义为：N是所有工序组成的节点集，其中0和*表示两个虚设的起始工序和终止工序，每个节点的权值等于此节点工序在对应机器上的加工时间；A是连接同一个工件的邻接工序的有向弧集，表示工序之间的先后加工顺序约束；E是连接在同一台机器上相邻加工工序间的析取弧集。E中的每个析取弧是双向的，可视为包含两个方向相反的弧，并且由每台机器i上的析取弧子集构成，即，Ei表示机器i（i∈Ω）上的析取弧子集。

4）柔性作业车间调度问题评价指标

在柔性作业车间调度问题的求解过程中，调度方案的优劣需要通过一定的目标函数来判断，目标函数也就是常用的评价指标。柔性作业车间调度问题中不仅包括了传统车间调度问题常用的评价指标，而且还有其他评价指标。下面列出较为常用的几个评价指标。

（1）最大完工时间最小。

完工时间是每个工件最后一道工序完成的时间，其中最大的那个时间就是最大完工时间。它是衡量调度方案的最根本指标，主要体现车间的生产效率，也是柔性作业车间调度问题研究中应用最广泛的评价指标之一，可用下式表示：

f1=min(max1≤j≤n(Cj))

（2）机器最大负荷最小。

在柔性作业车间调度问题的求解中，存在选择机器的过程，各台机器的负荷随着不同的调度方案而不同。负荷最大的机器就是瓶颈设备。要提高每台机器的利用率，必须使各台机器的负荷尽量小且平衡，可表示为：

（3）总机器负荷最小。

工序在不同机器上的加工时间是不同的，总的机器负荷随着不同的调度方案而不同。尽量在最大完工时间一样的情况下，减小所有机器的总消耗，可表示为：

以上几种性能评价指标较为常用。还有其他如考虑工件安装时间的性能评价指标或更加贴近生产成本的一些成本指标等。其中，如果性能评价指标是完工时间的非减函数，则称其为正规性能指标（regular measure）。

7.任务评价

任务评价见表6-1。

表6-1　任务评价