2.2 生產(chǎn)調(diào)度問題

生產(chǎn)調(diào)度問題是指在一定的時(shí)間內(nèi)，進(jìn)行可用共享資源的分配和生產(chǎn)任務(wù)的排序，以滿足某些指定的性能指標(biāo)，是非常復(fù)雜的問題，通常是多約束、多目標(biāo)、隨機(jī)不確定優(yōu)化問題。求解過程的計(jì)算隨問題規(guī)模呈指數(shù)增長(zhǎng)，已被證明是NP完全問題（Non-polynomial Complete Problems）（葉秉如，2001）。

生產(chǎn)調(diào)度問題一般可以描述為：針對(duì)某項(xiàng)可以分解的工作，在一定的約束條件下，如何安排其組成部分所占用的資源、加工時(shí)間及先后順序，以獲得產(chǎn)品制造時(shí)間或者成本等最優(yōu)。生產(chǎn)調(diào)度的任務(wù)是在滿足裝置設(shè)備和工藝要求的條件下，根據(jù)市場(chǎng)的需求，合理地安排與組織生產(chǎn)，以提高生產(chǎn)過程的最優(yōu)性，達(dá)到降低成本，提高企業(yè)利潤(rùn)的目的。影響生產(chǎn)調(diào)度的因素有：產(chǎn)品的投產(chǎn)期、生產(chǎn)能力、交貨期、加工設(shè)備和原料的可得性、加工順序、加工路徑、批量大小、成本限制等，這些都是所謂的約束條件。有些約束條件是必須滿足的，比如交貨期、生產(chǎn)能力等；有些只要達(dá)到一定的滿意度即可，比如生產(chǎn)成本及利潤(rùn)等；有些約束在進(jìn)行調(diào)度是可以看作確定性因素加以考慮，而有些因素在進(jìn)行調(diào)度時(shí)是事先無法預(yù)知的，可以作為不確定因素考慮，比如，設(shè)備故障、原料供應(yīng)、生產(chǎn)任務(wù)變化及能源的供應(yīng)等（王萬良、吳啟迪，2007）。

根據(jù)設(shè)備環(huán)境可將生產(chǎn)調(diào)度問題分為兩大類：面向機(jī)械加工的離散操作車間調(diào)度問題、面向流程工業(yè)的間隙生產(chǎn)調(diào)度（也稱為批處理調(diào)度）問題（徐建有，2015）。本章主要研究車間調(diào)度問題，按照加工設(shè)備環(huán)境，即工件在加工設(shè)備上的流動(dòng)方式，可以將車間調(diào)度問題分為以下幾類：?jiǎn)螜C(jī)調(diào)度問題（Single Machine Scheduling Problem）、并行機(jī)調(diào)度問題（Parallel Machine Scheduling Problem）、流水車間調(diào)度問題（Flow Shop Scheduling Problem）、異順序車間調(diào)度問題（Job Shop Scheduling Problem）。

車間調(diào)度模型通常采取三元素法“α|β|γ ”來表示（Graham et al.，1979）。

其中，α表示機(jī)器配置環(huán)境特征：1表示單機(jī)器生產(chǎn)；P表示平行機(jī)器生產(chǎn)；F表示流水線作業(yè)；J表示異順序作業(yè)。β表示一系列資源約束或者生產(chǎn)條件特征：r_j表示工件的準(zhǔn)備時(shí)間，指工件到達(dá)車間可以開始工作的最早時(shí)間；d_j表示工期即承諾的工件完成時(shí)間。如果工期必須滿足，也稱為最后期限。如果允許在工期內(nèi)完成，則目標(biāo)值受到懲罰；權(quán)重w_j表示工件的優(yōu)先權(quán)，即該工件在系統(tǒng)中相對(duì)于其他工件的重要程度；p_j表示工件在機(jī)器上的加工時(shí)間；s_ij表示兩個(gè)工件之間的機(jī)器準(zhǔn)備時(shí)間，即工件i完成生產(chǎn)后機(jī)器需維護(hù)一段時(shí)間后才能開始生產(chǎn)工件j。γ表示優(yōu)化問題的目標(biāo)函數(shù)：C_max表示最大完成時(shí)間，即最后一個(gè)工件完成的時(shí)間；∑C_j表示所有工件的完成時(shí)間之和；∑w_jC_j表示所有工件的加權(quán)完成時(shí)間之和；T_max表示最大延遲時(shí)間，即違反工期的最大時(shí)間；∑T_j表示所有工件的延遲時(shí)間之和；∑w_jT_j表示所有工件的加權(quán)延期時(shí)間之和；∑E_j表示所有工件的提前完成時(shí)間之和。

2.2.1 單機(jī)調(diào)度問題

最簡(jiǎn)單的加工環(huán)境，車間中只有一臺(tái)加工設(shè)備。在單機(jī)調(diào)度問題中，通常會(huì)有一個(gè)待加工工件集合，每個(gè)工件具有一定的加工時(shí)間、權(quán)重，以及相應(yīng)的交貨期要求等，并且在加工之前已經(jīng)到達(dá)。該問題的任務(wù)是確定一個(gè)最優(yōu)的工件加工順序，使得一個(gè)給定的目標(biāo)達(dá)到最優(yōu)化，例如每個(gè)工件完工時(shí)間之和最小、所有工件的延誤時(shí)間最小等（Fatih et al.，2006；Anghinolfi and Paolucci，2009；Wang and Tang，2010）。

常見的加工順序規(guī)則主要有以下幾種：

（1）FCFS（First Come，F(xiàn)irst Served）規(guī)則。即先進(jìn)先出規(guī)則，按照訂單的到達(dá)先后順序進(jìn)行加工。

（2）SPT（Shortest Processing Time）規(guī)則。即最短加工時(shí)間規(guī)則，按照各工件加工時(shí)間由小到大的順序進(jìn)行加工。

（3）EDD（Earliest Due Date）規(guī)則。即最早交貨期規(guī)則，按照各訂單交貨期的先后順序進(jìn)行加工。

2.2.2 并行機(jī)調(diào)度問題

并行機(jī)調(diào)度問題是加工系統(tǒng)有一組m臺(tái)功能相同的機(jī)器，待加工的工件都只有一道工序，在生產(chǎn)過程中，每個(gè)工件可以在任意一臺(tái)機(jī)器上完成加工，需要決策的是將工件分配到哪臺(tái)機(jī)器上進(jìn)行加工，以及各臺(tái)機(jī)器上所分配的工件之間的加工順序，以使得整個(gè)生產(chǎn)過程的某一指標(biāo)（最大完成時(shí)間、總加權(quán)流水時(shí)間、總加權(quán)拖期懲罰等）達(dá)到最優(yōu)化（Ou et al.，2015；Mensendiek et al.，2015）。通常采用LPT（The Longest Processing Time First Rule）準(zhǔn)則：將前m個(gè)加工時(shí)間最長(zhǎng)的工件先加工，一旦有機(jī)器完成加工，則該機(jī)器得到空閑，將剩余工件中加工時(shí)間最長(zhǎng)的工件進(jìn)行加工（靳志宏，2008）。

2.2.3 流水車間調(diào)度問題

流水車間調(diào)度問題一般可以描述為：n個(gè)工件在m臺(tái)機(jī)器上加工，一個(gè)工件分為k道工序，每道工序要求不同的機(jī)器加工。n個(gè)工件在m臺(tái)機(jī)器上的加工順序相同，工件i在機(jī)器j上的加工時(shí)間是給定的，目標(biāo)一般是求n個(gè)工件的最優(yōu)加工順序，使最大流程時(shí)間最小（Gupta，1988；Taillard，1990；Koulamas，1998）。兩臺(tái)機(jī)器的流水線排序通常采取Johnson算法：首先，列出各工件在各機(jī)床上加工所需的時(shí)間，并用矩陣形式表示；然后，選擇最小加工時(shí)間，如果該時(shí)間是在第一臺(tái)機(jī)器上，則將該工件放在靠前位置；反之，如果該時(shí)間是在第二臺(tái)機(jī)器上，則將該工件放在靠后位置。同時(shí)將該工件從矩陣中去掉。重復(fù)這一過程直至所有的工件被選擇為止（靳志宏，2008）。

2.2.4 異順序車間調(diào)度問題

異順序車間調(diào)度問題通常包含一組工件｛1，……，n｝和一系列機(jī)器｛1，2，……，m｝。和流水線車間不同，其中每個(gè)工件都有不同的加工路線，每道工序都必須在指定的機(jī)器上加工，該問題的優(yōu)化目標(biāo)是按照工件的加工路線，將每個(gè)工件的加工作業(yè)分配到各相關(guān)機(jī)器上，使得所得到的調(diào)度方案的完工時(shí)間最小或者延遲時(shí)間最小等。通常如下假設(shè)：基于每個(gè)工件所給定的加工路線，只有在前一道工序完成的情況下才能開始下一道工序的加工；某臺(tái)機(jī)器一旦開始某道工序的加工，則不允許中斷；在任意時(shí)刻，每臺(tái)機(jī)器最多只能加工一個(gè)工件（Sels et al.，2011；Gabel and Riedmiller，2012；Zhang et al.，2013）。