第1章　绪论

1.1　生产调度概述

生产调度（Production Scheduling）问题是依据生产计划拟定的生产任务，利用有限的生产资源（如机器、人员等），在满足一定约束的前提下，确定每个工件在机器上的加工顺序和时间参数，若存在平行机，还要为工件指派加工机器，以实现生产目标的优化。

调度问题是一类经典的组合优化问题，大多具有“NP-难”（NP-hard）的复杂性，相关研究能够在学术上丰富和完善组合优化理论与算法的研究。同时，生产调度具有很强的工程背景，是现代制造系统，例如，制造执行系统（Manufacturing Execution System，MES）、高级计划与排程（Advanced Planning and Scheduling，APS）等的重要决策问题，在空间上将生产计划细化到每个工件和单台机器，在时间上根据生产节奏精确到分钟调度甚至是秒调度，能够直接用于指导生产过程，并及时响应生产中的动态变化，对于生产管理过程优化的实践具有重要的指导意义，有利于提高设备利用率、降低生产成本、减少生产能耗等，进而增强企业的竞争优势。

在生产过程中，机器的种类、数量和特征构成了调度问题的生产环境。根据生产环境的不同特点，调度问题可以分为单机调度问题、平行机调度问题和车间调度问题。

单机（Single Machine）调度问题，即只有一台加工机器的调度问题，是调度领域最为简单的基本问题，对其他调度问题具有重要的指导意义。

平行机（Parallel Machine）调度问题，即由多台具有相同功能的机器构成的调度环境，换言之，每个工件只经过一个阶段的加工，且此阶段存在若干台加工机器。根据机器加工速度的不同，平行机调度问题可以进一步分为：①同速机（Identical Machine），即所有的机器具有相同的速度；②恒速机（Uniform Machine），即机器的速度为恒定常数，与工件无关；③变速机（Unrelated Machine），即机器速度不同，且依赖于加工工件。

车间调度问题，即在生产环境中，存在多台具有不同功能的机器，工件需要经过多台不同的机器（对应多个生产阶段）才能完成加工。根据工件的加工路径特征，车间调度问题可以进一步分为流水车间调度问题、作业车间调度问题、开放车间调度问题、混合流水车间调度问题等。

第一，流水车间（Flow Shop）调度问题。即每个阶段仅有一台机器，每个工件以相同的顺序经过各个阶段，换言之，所有工件的加工路径是相同的。流水车间调度问题是车间调度中最基础的一类问题，然而，即使这类车间调度中相对简单的问题，其求解难度也与非对称TSP问题的难度相当。

第二，作业车间（Job Shop）调度问题。即每个阶段仅有一台机器，每个工件经过各阶段的顺序已定，换言之，各个工件有自己的加工路径。当所有工件的加工路径相同时，作业车间调度问题即为流水车间调度问题。

第三，开放车间（Open Shop）调度问题。即每个阶段仅有一台机器，每个工件可以按照任意顺序加工，换言之，每个工件的加工路径并未指定，需要在调度过程中确定。

第四，混合流水车间（Hybrid Flowshop）调度问题。混合流水车间是流水车间和平行机的推广，即所有工件经过各阶段的路径是相同的，且至少一个阶段存在多台平行机。

由生产调度的定义可以看出，生产环境、约束条件和优化目标是组成调度问题的三要素。由于生产环境具有不同的特征，工件和资源的约束条件错综复杂，再加上度量不同指标的目标函数，形成了种类繁多的生产调度问题。对于调度问题，通常采用Graham等[1]提出的三元组表示法α｜β｜γ描述，其中，α表示生产环境，β表示问题约束和特征，γ表示优化目标。

α域表示调度问题的生产环境，主要有以下几项：1表示单机调度环境；Pm、Qm、Rm分别表示由m台同速机、恒速机和变速机组成的并行机环境；Fm表示具有m台机器的流水车间调度环境；Jm表示具有m台机器的作业车间调度环境；Om表示具有m台机器的开放车间调度环境；FHs表示由s个阶段构成的混合流水车间调度环境。

β域列举了工件特征、工艺要求、资源限制等约束条件，其可能的取值如下：r_i表示工件J_i的释放时间（Release Date），如果β域不出现r_i，则表示不存在释放时间约束，即r_i=0；prmp表示工件加工时允许中断，如果β域不出现prmp，则表示工件加工时不允许中断；prec、chains、tree表示工件的相关性，分别表示一般优先约束、链优先约束和树型优先约束，如果β域不出现这些项，则表示工件之间无关；no-idle表示不允许机器在加工过程中出现空闲时间；prmu表示工件始终按照通过第一台机器的顺序来通过所有机器，此约束只存在于流水车间环境，具有这一特征的流水车间调度问题被称为排列排序问题（Permutation Scheduling）；nwt表示无等待（No-wait）约束，不允许工件在相邻阶段间等待，存在于具有多阶段加工的车间调度，是等待时间上限约束的一类特殊情况。

γ域表示问题的优化目标，令C_i表示工件J_i在最后阶段的完工时间，d_i表示J_i的交货期，n表示工件总数，则γ域常见的取值如下：C_max，最大完工时间（Makespan），；，加权总完工时间（Total Weighted Completion Time），；当权重相同时，加权总完工时间为总完工时间（Total Completion Time），；L_max，最大延误（Maximum Lateness），；其中，L_i=C_i-d_i表示工件J_i的延误时间；T_max，最大拖期（Maximum Tardiness）， ，其中，表示工件J_i的拖期时间；∑U_i，误工工件数（Number of Tardy Jobs），，其中，U_i∈{0，1}表示工件拖期的单位惩罚。