2.2 生產調度問題
生產調度問題是指在一定的時間內，進行可用共享資源的分配和生產任務的排序，以滿足某些指定的性能指標，是非常復雜的問題，通常是多約束、多目標、隨機不確定優化問題。求解過程的計算隨問題規模呈指數增長，已被證明是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表示異順序作業。β表示一系列資源約束或者生產條件特征：rj表示工件的準備時間，指工件到達車間可以開始工作的最早時間；dj表示工期即承諾的工件完成時間。如果工期必須滿足，也稱為最后期限。如果允許在工期內完成，則目標值受到懲罰；權重wj表示工件的優先權，即該工件在系統中相對于其他工件的重要程度；pj表示工件在機器上的加工時間；sij表示兩個工件之間的機器準備時間，即工件i完成生產后機器需維護一段時間后才能開始生產工件j。γ表示優化問題的目標函數：Cmax表示最大完成時間，即最后一個工件完成的時間；∑Cj表示所有工件的完成時間之和；∑wjCj表示所有工件的加權完成時間之和；Tmax表示最大延遲時間，即違反工期的最大時間；∑Tj表示所有工件的延遲時間之和；∑wjTj表示所有工件的加權延期時間之和；∑Ej表示所有工件的提前完成時間之和。
2.2.1 單機調度問題
最簡單的加工環境，車間中只有一臺加工設備。在單機調度問題中，通常會有一個待加工工件集合，每個工件具有一定的加工時間、權重，以及相應的交貨期要求等，并且在加工之前已經到達。該問題的任務是確定一個最優的工件加工順序，使得一個給定的目標達到最優化，例如每個工件完工時間之和最小、所有工件的延誤時間最小等（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）規則。即最早交貨期規則，按照各訂單交貨期的先后順序進行加工。
2.2.2 并行機調度問題
并行機調度問題是加工系統有一組m臺功能相同的機器，待加工的工件都只有一道工序，在生產過程中，每個工件可以在任意一臺機器上完成加工，需要決策的是將工件分配到哪臺機器上進行加工，以及各臺機器上所分配的工件之間的加工順序，以使得整個生產過程的某一指標（最大完成時間、總加權流水時間、總加權拖期懲罰等）達到最優化（Ou et al.，2015；Mensendiek et al.，2015）。通常采用LPT（The Longest Processing Time First Rule）準則：將前m個加工時間最長的工件先加工，一旦有機器完成加工，則該機器得到空閑，將剩余工件中加工時間最長的工件進行加工（靳志宏，2008）。
2.2.3 流水車間調度問題
流水車間調度問題一般可以描述為：n個工件在m臺機器上加工，一個工件分為k道工序，每道工序要求不同的機器加工。n個工件在m臺機器上的加工順序相同，工件i在機器j上的加工時間是給定的，目標一般是求n個工件的最優加工順序，使最大流程時間最?。℅upta，1988；Taillard，1990；Koulamas，1998）。兩臺機器的流水線排序通常采取Johnson算法：首先，列出各工件在各機床上加工所需的時間，并用矩陣形式表示；然后，選擇最小加工時間，如果該時間是在第一臺機器上，則將該工件放在靠前位置；反之，如果該時間是在第二臺機器上，則將該工件放在靠后位置。同時將該工件從矩陣中去掉。重復這一過程直至所有的工件被選擇為止（靳志宏，2008）。
2.2.4 異順序車間調度問題
異順序車間調度問題通常包含一組工件｛1，……，n｝和一系列機器｛1，2，……，m｝。和流水線車間不同，其中每個工件都有不同的加工路線，每道工序都必須在指定的機器上加工，該問題的優化目標是按照工件的加工路線，將每個工件的加工作業分配到各相關機器上，使得所得到的調度方案的完工時間最小或者延遲時間最小等。通常如下假設：基于每個工件所給定的加工路線，只有在前一道工序完成的情況下才能開始下一道工序的加工；某臺機器一旦開始某道工序的加工，則不允許中斷；在任意時刻，每臺機器最多只能加工一個工件（Sels et al.，2011；Gabel and Riedmiller，2012；Zhang et al.，2013）。