[科普中國]-排序問題

排序的基本概念

排序問題已被廣泛應(yīng)用于生產(chǎn)管理、計(jì)算機(jī)系統(tǒng)、運(yùn)輸調(diào)度等領(lǐng)域。排序問題是一類重要的組合優(yōu)化問題。一般來說，凡是有多個(gè)不同的任務(wù)要完成，就有作業(yè)排序與作業(yè)計(jì)劃問題。幾批不同的工件要加工，幾個(gè)程序等待要運(yùn)行，幾個(gè)問題要處理等，都有作業(yè)排序。這些問題的共同特征是要將不同的工作任務(wù)安排一個(gè)執(zhí)行的順序和時(shí)間．使得目標(biāo)最優(yōu)化。所以．作業(yè)排序?qū)嵸|(zhì)上是要解決如何按時(shí)間的先后，將有限的資源分配給不同的工作任務(wù)，使預(yù)定的目標(biāo)最優(yōu)化的問題。

需要說明的是，在生產(chǎn)運(yùn)作管理中常用到編制作業(yè)計(jì)劃、排序、調(diào)度、派工、控制、趕工等名詞。一般來說，作業(yè)排序只確定工件在機(jī)器上的加工順序，而編制作業(yè)計(jì)劃不僅確定工件的加工順序，而且還包括確定每個(gè)工件的開始時(shí)間和完成時(shí)間，這樣才能指導(dǎo)工人的生產(chǎn)活動(dòng)。由于當(dāng)各臺(tái)機(jī)器上工件的加工順序確定后，就可以按最早可能開始時(shí)間安排所有工件的計(jì)劃，這樣初始可行的作業(yè)計(jì)劃就可以編制好，因而編制作業(yè)計(jì)劃的問題之一就是作業(yè)排序問題。派工是按作業(yè)計(jì)劃的要求，將具體的牛產(chǎn)任務(wù)安排到具體的機(jī)器上并交給相應(yīng)的操作工人負(fù)責(zé)；控制是監(jiān)控實(shí)際生產(chǎn)過程．并使其和計(jì)劃保證一致的過程；調(diào)度是在加工制造發(fā)生之后，發(fā)現(xiàn)實(shí)際進(jìn)度已經(jīng)偏離計(jì)劃而采取的調(diào)配資源的行動(dòng)，調(diào)度屬于控制的范圍；而趕工是在實(shí)際進(jìn)度已經(jīng)落后于計(jì)劃進(jìn)度時(shí)采取的追趕進(jìn)度的行動(dòng)，趕工屬于調(diào)度的范圍。如火車時(shí)刻表是事先確定的一種作業(yè)計(jì)劃，各列火車都按該計(jì)劃來執(zhí)行；在實(shí)際執(zhí)行過程需要監(jiān)控所有火車運(yùn)行情況，根據(jù)這些運(yùn)行信息相應(yīng)采取措施以確保計(jì)劃的完成，這種監(jiān)控采取的預(yù)防和實(shí)際措施的過程就是控制；其中實(shí)際運(yùn)行情況偏離了計(jì)劃所采取的措施就是調(diào)度；如果火車發(fā)生晚點(diǎn)，采取加快運(yùn)行速度來趕上計(jì)劃時(shí)間就是趕工2。

排序問題的描述最初的排序研究與應(yīng)用主要是針對(duì)加工制造企業(yè)，一般使用機(jī)器、工件、加工路線、工序和加工時(shí)間來描述一個(gè)排序作業(yè)的任務(wù)。即假定有n個(gè)工件要按一定的加工路線經(jīng)過m臺(tái)機(jī)器加工，其中加工路線是由工件加工的工藝過程決定的，是工件加工在技術(shù)上的約束，是工件所需要的加工工序的順序。而排序就是確定這n個(gè)工件在m臺(tái)機(jī)器上加工的先后順序。隨著排序在其他各行各業(yè)的應(yīng)用，原有的“機(jī)器”、“工件”、“工序”和“加工時(shí)間”的意義已經(jīng)發(fā)生了變化，如“機(jī)器”的意義已經(jīng)擴(kuò)展到“服務(wù)者”，“工件”則泛指“服務(wù)對(duì)象”，“工序”則指“服務(wù)活動(dòng)”，“加工時(shí)間”則是“服務(wù)時(shí)間”。如計(jì)算機(jī)網(wǎng)絡(luò)的服務(wù)器（機(jī)器）同時(shí)接到多個(gè)電郵請(qǐng)求（工件），處理后發(fā)到請(qǐng)求的用戶信箱；多艘輪船（工件）同時(shí)要?？看a頭（機(jī)器）；維修工人（機(jī)器）維修多個(gè)機(jī)器設(shè)備（工件）等2。

機(jī)器只有一臺(tái)機(jī)器的排序問題稱為單機(jī)排序問題，否則稱為多機(jī)排序問題。

在多機(jī)問題中機(jī)器分為兩大類：通用平行(parallel)機(jī)和專用串聯(lián)(dedicated)機(jī)，如果所有機(jī)器的功能相同，稱為同類機(jī)或平行機(jī)，即一個(gè)工件需要在多臺(tái)平行機(jī)的一個(gè)機(jī)器上加工一次；而串聯(lián)機(jī)則是機(jī)器具有不同的功能，工件需要在不同的機(jī)器上加工。

平行機(jī)又可分成3類：具有相同速度的同速(identical)機(jī)、具有不同加工速度但此速度不依賴于工件的恒速( uniform)機(jī)和隨加工的工件不同加速度也不同的變速(unrelated)機(jī)。

串聯(lián)機(jī)也可分為3類：第一個(gè)工件以特定的相同機(jī)器順序加工的流水作業(yè)(flow shop)、工件依次在機(jī)器上加工的次序可以任意的開放作業(yè)(open shop)和每一工件以各自特定的機(jī)器次序進(jìn)行加工的單件作業(yè)(job shop)。

還有一類更復(fù)雜的情況，就是柔性流水作業(yè)(flexible flow shop)，它是流水作業(yè)和平行機(jī)的推廣。在柔性流水作業(yè)中，有多類機(jī)器，每個(gè)工件有多道工序，每道工序需要在每類機(jī)器中的一臺(tái)機(jī)器上加工，且每個(gè)工件的加工順序相同。機(jī)器的分類情況見圖12。

工件和工序?qū)Σ辉试S中斷加工的情況來說，一個(gè)工件（ ）在一臺(tái)機(jī)器( )上連續(xù)加工的過程稱為工序****(operation)。按工件到達(dá)車間的不同，可以將排序分為靜態(tài)和動(dòng)態(tài)兩種。當(dāng)進(jìn)行排序時(shí)所有工件都已經(jīng)到達(dá)，可以一次對(duì)它們進(jìn)行排序，這是靜態(tài)排序問題；若工件是陸續(xù)到達(dá)的，要隨時(shí)對(duì)它們進(jìn)行排序，這是動(dòng)態(tài)排序問題。

排序中的約束條件，主要指的是工件的性質(zhì)以及它們?cè)诩庸み^程中的要求和限制。

1)加工時(shí)間

一個(gè)工件的加工時(shí)間： ；n個(gè)工件的加工時(shí)間則用矩陣來表示：

式中： ——工件 在機(jī)器i 上所需要的加工時(shí)間。

2)到達(dá)時(shí)間(arrival time)或就緒時(shí)間(ready time)

到達(dá)時(shí)間或就緒時(shí)間 是工件已經(jīng)準(zhǔn)備好可以馬上被加工的時(shí)間。若所有工件的就緒時(shí)間相同，則取 。

3)工件工期(due date)或截止期限(deadline)

工期dj表示對(duì)工件限定的完工時(shí)間。若不按期完工，就會(huì)受到一定的懲罰。絕對(duì)不允許延誤的工期稱為截止期限。

4)工件權(quán)重(weight)

工件權(quán)重是相對(duì)于其他工件而言工件的重要性程度2。

目標(biāo)函數(shù)用表示工件的完工時(shí)間。一般來說，要使完工時(shí)間的函數(shù)達(dá)到極小化。在排序問題中，目標(biāo)函數(shù)主要有以下幾種。

1)最大完工時(shí)間或時(shí)間表長(schedule length，make-span)

時(shí)間表長可定義為：，即為最后一個(gè)被加工完的工件的完工時(shí)間。

2)加權(quán)流程時(shí)間(weighted flow time)和加權(quán)完工時(shí)間

一個(gè)工件的流程時(shí)間是指工件從到達(dá)系統(tǒng)開始一直到加工完為止的時(shí)間，包括在系統(tǒng)中的等待時(shí)間和加工時(shí)間：。

系統(tǒng)的平均加權(quán)流程時(shí)間：。

將上述平均流程時(shí)間轉(zhuǎn)換一下：由于第二項(xiàng)是常數(shù)，第一項(xiàng)的分母也是常數(shù)，因此極小化平均加權(quán)流程時(shí)間相當(dāng)于極小化總加權(quán)完工時(shí)間(total weighted completion time)：

3)最大延誤時(shí)間(maximum lateness)

工件的延誤時(shí)間定義為最大延誤時(shí)間。

4)加權(quán)總誤工(total weighted tardiness)

一個(gè)工件當(dāng)其完工時(shí)間大于其完工期限時(shí)稱為誤工：

加權(quán)總誤工：

5)加權(quán)誤工工件數(shù)(weighted number of tardy jobs)

用0/1來表示某工件是否誤工：

加權(quán)誤工件數(shù)：

總之，在排序中，工件是被加工的對(duì)象，是要完成的任務(wù)；機(jī)器是提供加工的對(duì)象，是完成任務(wù)所需要的資源；排序是安排一個(gè)時(shí)間表，以在一定約束條件下對(duì)工件和機(jī)器按時(shí)間進(jìn)行分配和安排次序，使某一或一些目標(biāo)達(dá)到最優(yōu)2。

排序問題的分類與表示方法排序問題的類別有多種劃分方法，如前面按機(jī)器、按工件有不同的劃分方法，另外根據(jù)參數(shù)的性質(zhì)還可以劃分為確定型與隨機(jī)型排序，即加工時(shí)間和其他有關(guān)參數(shù)是已經(jīng)知道的、確定的量，就稱為確定型排序；而加工時(shí)間和相關(guān)參數(shù)是隨機(jī)型的量則稱為隨機(jī)型排序。由機(jī)器、工件、加工參數(shù)和目標(biāo)函數(shù)的不同特征及其他方面的差別，構(gòu)成了多種不同的排序問題。這里采用國際上使用的三參數(shù)表示方法來描述排序問題，即。

域表示機(jī)器的數(shù)量、類型和環(huán)境：，其中，各符號(hào)分別代表單機(jī)、同速機(jī)、恒速機(jī)、自由作業(yè)、流水作業(yè)、單件作業(yè)和柔性流水作業(yè)；，分別表示機(jī)器的數(shù)目不確定和有m臺(tái)機(jī)器。

域表示工件的性質(zhì)、加工要求和限制，資源的種類、數(shù)量和對(duì)加工的影響等，它可以同時(shí)包含多項(xiàng)，可能的主項(xiàng)有：（工件有不同的到達(dá)時(shí)間）、（工件順序加工的設(shè)備調(diào)整時(shí)間）、prmp（允許中斷）等。

域表示要優(yōu)化的目標(biāo)函數(shù)：（時(shí)間表長）、（加權(quán)總完工時(shí)間）、（最大延誤時(shí)間）、（加權(quán)總誤工）、（加權(quán)誤工件數(shù)）等。

如表示單機(jī)排序問題，目標(biāo)函數(shù)是總延誤時(shí)間最??；表示有m臺(tái)同速機(jī)的排序問題，目標(biāo)函數(shù)是極小化時(shí)間表長；而表示一個(gè)由m臺(tái)機(jī)器組成的流水作業(yè)排序問題，每個(gè)作業(yè)的所有工序的加工時(shí)間都相等，目標(biāo)是加權(quán)總完工時(shí)間最小；表示兩臺(tái)機(jī)器單件作業(yè)排序問題，每個(gè)工件在每臺(tái)機(jī)器上至多加工一次，其目標(biāo)函數(shù)是時(shí)間表長最小2。

排序問題的求解可行排序與最優(yōu)排序排序問題是一類組合優(yōu)化問題，由于在實(shí)際生產(chǎn)中，排序問題中的機(jī)器、工序、資源都是有限的，絕大部分排序問題是從有限個(gè)可行解中找出一個(gè)最優(yōu)解，使目標(biāo)函數(shù)達(dá)到極小。

三種計(jì)劃車間作業(yè)計(jì)劃可能存在著很多可行的作業(yè)計(jì)劃安排方法，其中各工序都按最早可能加工或完工時(shí)間安排的作業(yè)計(jì)劃稱為半能動(dòng)計(jì)劃( semi-active schedule)；若半能動(dòng)計(jì)劃中任何一臺(tái)機(jī)器的每段空閑時(shí)間都不足以加工一道加工工序的，稱為能動(dòng)作業(yè)計(jì)劃(active schedule)；若在能動(dòng)計(jì)劃中，沒有任何延遲(delay)現(xiàn)象出現(xiàn)，則稱為無延遲作業(yè)計(jì)劃(non-delay schedule)，這里的無延遲是指如果有準(zhǔn)備好的被加工的T序，不準(zhǔn)許有空閑的機(jī)器出現(xiàn)，該計(jì)劃相當(dāng)于不允許強(qiáng)迫機(jī)器空閑。

對(duì)于大多數(shù)排序問題，包括所有可中斷排序問題，最優(yōu)排序是無延遲排序，但也有一些不可中斷的排序問題是延遲排序2。