下载掌阅APP，畅读海量书库
立即打开
生产调度问题是指在一定的时间内，进行可用共享资源的分配和生产任务的排序，以满足某些指定的性能指标，是非常复杂的问题，通常是多约束、多目标、随机不确定优化问题。求解过程的计算随问题规模呈指数增长，已被证明是NP完全问题（Non-polynomial Complete Problems）（叶秉如，2001）。
生产调度问题一般可以描述为：针对某项可以分解的工作，在一定的约束条件下，如何安排其组成部分所占用的资源、加工时间及先后顺序，以获得产品制造时间或者成本等最优。生产调度的任务是在满足装置设备和工艺要求的条件下，根据市场的需求，合理地安排与组织生产，以提高生产过程的最优性，达到降低成本，提高企业利润的目的。影响生产调度的因素有：产品的投产期、生产能力、交货期、加工设备和原料的可得性、加工顺序、加工路径、批量大小、成本限制等，这些都是所谓的约束条件。有些约束条件是必须满足的，比如交货期、生产能力等；有些只要达到一定的满意度即可，比如生产成本及利润等；有些约束在进行调度是可以看作确定性因素加以考虑，而有些因素在进行调度时是事先无法预知的，可以作为不确定因素考虑，比如，设备故障、原料供应、生产任务变化及能源的供应等（王万良、吴启迪，2007）。
根据设备环境可将生产调度问题分为两大类：面向机械加工的离散操作车间调度问题、面向流程工业的间隙生产调度（也称为批处理调度）问题（徐建有，2015）。本章主要研究车间调度问题，按照加工设备环境，即工件在加工设备上的流动方式，可以将车间调度问题分为以下几类：单机调度问题（Single Machine Scheduling Problem）、并行机调度问题（Parallel Machine Scheduling Problem）、流水车间调度问题（Flow Shop Scheduling Problem）、异顺序车间调度问题（Job Shop Scheduling Problem）。
车间调度模型通常采取三元素法“ α | β | γ ”来表示（Graham et al.，1979）。
其中， α 表示机器配置环境特征：1表示单机器生产；P表示平行机器生产；F表示流水线作业；J表示异顺序作业。 β 表示一系列资源约束或者生产条件特征：r j 表示工件的准备时间，指工件到达车间可以开始工作的最早时间；d j 表示工期即承诺的工件完成时间。如果工期必须满足，也称为最后期限。如果允许在工期内完成，则目标值受到惩罚；权重w j 表示工件的优先权，即该工件在系统中相对于其他工件的重要程度；p j 表示工件在机器上的加工时间；s ij 表示两个工件之间的机器准备时间，即工件i完成生产后机器需维护一段时间后才能开始生产工件j。 γ 表示优化问题的目标函数： C max 表示最大完成时间，即最后一个工件完成的时间；∑ C j 表示所有工件的完成时间之和；∑ w j C j 表示所有工件的加权完成时间之和； T max 表示最大延迟时间，即违反工期的最大时间；∑ T j 表示所有工件的延迟时间之和；∑ w j T j 表示所有工件的加权延期时间之和；∑ E j 表示所有工件的提前完成时间之和。
最简单的加工环境，车间中只有一台加工设备。在单机调度问题中，通常会有一个待加工工件集合，每个工件具有一定的加工时间、权重，以及相应的交货期要求等，并且在加工之前已经到达。该问题的任务是确定一个最优的工件加工顺序，使得一个给定的目标达到最优化，例如每个工件完工时间之和最小、所有工件的延误时间最小等（Fatih et al.，2006；Anghinolfi and Paolucci，2009；Wang and Tang，2010）。
常见的加工顺序规则主要有以下几种：
（1）FCFS（First Come，First Served）规则。即先进先出规则，按照订单的到达先后顺序进行加工。
（2）SPT（Shortest Processing Time）规则。即最短加工时间规则，按照各工件加工时间由小到大的顺序进行加工。
（3）EDD（Earliest Due Date）规则。即最早交货期规则，按照各订单交货期的先后顺序进行加工。
并行机调度问题是加工系统有一组 m 台功能相同的机器，待加工的工件都只有一道工序，在生产过程中，每个工件可以在任意一台机器上完成加工，需要决策的是将工件分配到哪台机器上进行加工，以及各台机器上所分配的工件之间的加工顺序，以使得整个生产过程的某一指标（最大完成时间、总加权流水时间、总加权拖期惩罚等）达到最优化（Ou et al.，2015；Mensendiek et al.，2015）。通常采用LPT（The Longest Processing Time First Rule）准则：将前m个加工时间最长的工件先加工，一旦有机器完成加工，则该机器得到空闲，将剩余工件中加工时间最长的工件进行加工（靳志宏，2008）。
流水车间调度问题一般可以描述为：n个工件在m台机器上加工，一个工件分为k道工序，每道工序要求不同的机器加工。n个工件在m台机器上的加工顺序相同，工件i在机器j上的加工时间是给定的，目标一般是求n个工件的最优加工顺序，使最大流程时间最小（Gupta，1988；Taillard，1990；Koulamas，1998）。两台机器的流水线排序通常采取Johnson算法：首先，列出各工件在各机床上加工所需的时间，并用矩阵形式表示；然后，选择最小加工时间，如果该时间是在第一台机器上，则将该工件放在靠前位置；反之，如果该时间是在第二台机器上，则将该工件放在靠后位置。同时将该工件从矩阵中去掉。重复这一过程直至所有的工件被选择为止（靳志宏，2008）。
异顺序车间调度问题通常包含一组工件｛1，……，n｝和一系列机器｛1，2，……，m｝。和流水线车间不同，其中每个工件都有不同的加工路线，每道工序都必须在指定的机器上加工，该问题的优化目标是按照工件的加工路线，将每个工件的加工作业分配到各相关机器上，使得所得到的调度方案的完工时间最小或者延迟时间最小等。通常如下假设：基于每个工件所给定的加工路线，只有在前一道工序完成的情况下才能开始下一道工序的加工；某台机器一旦开始某道工序的加工，则不允许中断；在任意时刻，每台机器最多只能加工一个工件（Sels et al.，2011；Gabel and Riedmiller，2012；Zhang et al.，2013）。