1、李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第1頁(yè),生產(chǎn)運(yùn)作管理,第5章 生產(chǎn)調(diào)度,本章目錄,第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化 第2節(jié)：生產(chǎn)調(diào)度問(wèn)題的符號(hào)表示與分類 第3節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)題及其啟發(fā)式規(guī)則 第4節(jié)：生產(chǎn)調(diào)度問(wèn)題求解舉例,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第2頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(1)調(diào)度問(wèn)題舉例 生產(chǎn)調(diào)度屬于企業(yè)的微觀管理層次。 企業(yè)在組織生產(chǎn)時(shí)必須充分考慮到企業(yè)內(nèi)部人力、物力、財(cái)力以及企業(yè)外部供應(yīng)鏈條件及國(guó)家法律對(duì)生態(tài)、環(huán)境保護(hù)的規(guī)定等多方面的約束，在此前提下盡可能利潤(rùn)最大化并提高客戶滿意度。企業(yè)

2、生產(chǎn)過(guò)程中存在如下一類問(wèn)題，主要研究如何充分利用企業(yè)內(nèi)部的生產(chǎn)設(shè)備，盡可能提高客戶滿意度與企業(yè)利潤(rùn)，因此需要將待加工的任務(wù)或作業(yè)分配到一些機(jī)器上按照某種次序依次加工，這類問(wèn)題統(tǒng)稱為生產(chǎn)調(diào)度問(wèn)題或排序問(wèn)題。可見(jiàn)，生產(chǎn)調(diào)度旨在充分利用現(xiàn)有一定的資源，在滿足一些必須條件的基礎(chǔ)上，完成一定的任務(wù)并達(dá)到特定的調(diào)度目標(biāo)，因此它本身就是一類典型的優(yōu)化問(wèn)題。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第3頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(1)調(diào)度問(wèn)題舉例 一個(gè)車間要加工一批零件，每一個(gè)零件都具有相同的工序，即按照相同的順序在幾個(gè)不同的機(jī)床上加工。每個(gè)零件在每個(gè)機(jī)床上的加工時(shí)間

3、可能不同。調(diào)度的目標(biāo)是使得加工完所有零件的時(shí)間最短。這是一個(gè)流水線調(diào)度問(wèn)題。 在汽車生產(chǎn)的焊裝過(guò)程中，若干焊裝工業(yè)機(jī)器人在盡量少的時(shí)間內(nèi)完成一個(gè)整車3000多個(gè)焊點(diǎn)的焊裝任務(wù)，最后一個(gè)焊點(diǎn)的焊裝完成時(shí)間標(biāo)志著所有焊裝任務(wù)的完成，這就對(duì)應(yīng)一個(gè)最小化最大完工時(shí)間的平行機(jī)調(diào)度問(wèn)題。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第4頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(1)調(diào)度問(wèn)題舉例 對(duì)于這樣一些生產(chǎn)調(diào)度問(wèn)題， 我們通常將機(jī)床、焊裝工業(yè)機(jī)器人等抽象為機(jī)器(machine)； 將零件、焊裝點(diǎn)的焊裝任務(wù)等抽象為作業(yè)(job)； 調(diào)度問(wèn)題的一個(gè)可行解是一個(gè)加工這些作業(yè)的序列；

4、調(diào)度問(wèn)題的最優(yōu)解則是眾多可行解中使得目標(biāo)函數(shù)最優(yōu)的可行解。 生產(chǎn)調(diào)度問(wèn)題是一類典型的優(yōu)化問(wèn)題，它旨在充分利用現(xiàn)有一定的資源，在滿足一些必須條件的基礎(chǔ)上，完成一定的任務(wù)并達(dá)到特定的調(diào)度目標(biāo)。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第5頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(1)調(diào)度問(wèn)題舉例-制造系統(tǒng)中的生產(chǎn)調(diào)度：,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第6頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(1)調(diào)度問(wèn)題舉例 生產(chǎn)調(diào)度是為了實(shí)現(xiàn)生產(chǎn)計(jì)劃的一個(gè)資源優(yōu)化配置問(wèn)題，是制造業(yè)系統(tǒng)中的一個(gè)重要環(huán)節(jié)。然而，調(diào)度問(wèn)題遠(yuǎn)遠(yuǎn)不只是生產(chǎn)過(guò)程中的調(diào)度問(wèn)

5、題，它廣泛存在于計(jì)算機(jī)系統(tǒng)、交通、醫(yī)院、學(xué)校、服務(wù)業(yè)等。 服務(wù)系統(tǒng)中的生產(chǎn)調(diào)度：,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第7頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(1)調(diào)度問(wèn)題舉例 一個(gè)大型超市共有50個(gè)收銀臺(tái)，每個(gè)收銀臺(tái)有一個(gè)收銀員。每個(gè)收銀員的收銀速度（一個(gè)單位時(shí)間內(nèi)平均掃描條形碼的次數(shù)）相對(duì)恒定。目標(biāo)是在盡量短的時(shí)間內(nèi)滿足更多用戶的收銀任務(wù)。由于收銀員收銀速度差異相對(duì)恒定，這是一個(gè)同類機(jī)調(diào)度問(wèn)題。 某高校擴(kuò)大招生數(shù)量，原來(lái)針對(duì)學(xué)生的網(wǎng)絡(luò)服務(wù)器已遠(yuǎn)遠(yuǎn)不能滿足學(xué)生的需要，為了提高網(wǎng)絡(luò)服務(wù)質(zhì)量，在原先網(wǎng)絡(luò)服務(wù)器的基礎(chǔ)上購(gòu)置了1臺(tái)新的服務(wù)器，并構(gòu)建了由2臺(tái)服務(wù)器組

6、成的計(jì)算機(jī)機(jī)群（集群）系統(tǒng)。由于這2臺(tái)服務(wù)器之間存在恒定的速度差異，這也是一個(gè)同類機(jī)調(diào)度問(wèn)題。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第8頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(2)調(diào)度問(wèn)題是優(yōu)化問(wèn)題 優(yōu)化是研究如何充分利用時(shí)間、設(shè)備、成本、人力等有限的資源，達(dá)到某一或某些最優(yōu)目標(biāo)的理論，通常采用定量的研究方法。 對(duì)于現(xiàn)實(shí)生產(chǎn)生活中的優(yōu)化問(wèn)題，通常需要為之建立相應(yīng)的優(yōu)化模型，從而避免問(wèn)題定義的二義性，然后在此基礎(chǔ)上設(shè)計(jì)一定的優(yōu)化算法以獲得問(wèn)題的最優(yōu)解或高質(zhì)量滿意解。 因此，優(yōu)化主要包括優(yōu)化問(wèn)題與優(yōu)化方法兩個(gè)方面，而優(yōu)化問(wèn)題一般采用優(yōu)化模型來(lái)描述。,李凱(合肥工業(yè)

7、大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第9頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(2)調(diào)度問(wèn)題是優(yōu)化問(wèn)題 由于優(yōu)化模型是實(shí)際優(yōu)化問(wèn)題的數(shù)學(xué)描述，因此它也包括目標(biāo)函數(shù)和約束條件兩個(gè)部分。 根據(jù)目標(biāo)個(gè)數(shù)不同可以將優(yōu)化問(wèn)題分為單目標(biāo)優(yōu)化問(wèn)題和多目標(biāo)優(yōu)化問(wèn)題。 一個(gè)單目標(biāo)優(yōu)化問(wèn)題通常可以建立如下典型模型： ，其中是全部解空間，S是解空間中滿足約束條件的解的集合，而 是S 中的某一個(gè)解，被稱為可行解。問(wèn)題的目標(biāo)是尋找一個(gè)最優(yōu)解 ，使得 。 目標(biāo)最大化的優(yōu)化問(wèn)題可以轉(zhuǎn)化為目標(biāo)最小化的形式。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第10頁(yè),第1節(jié)：

8、生產(chǎn)調(diào)度與優(yōu)化,(2)調(diào)度問(wèn)題是優(yōu)化問(wèn)題 多目標(biāo)優(yōu)化問(wèn)題的優(yōu)化目標(biāo)多于一個(gè)，可以建立如下形式的模型： ， 其中 是一個(gè)非空集合， 是一個(gè)函數(shù)向量，因此多目標(biāo)優(yōu)化又稱為向量?jī)?yōu)化。 多目標(biāo)優(yōu)化問(wèn)題通常包含若干具有沖突的目標(biāo)，因此往往難以保證所有目標(biāo)同時(shí)達(dá)到最優(yōu)。Pareto提出了Pareto最優(yōu)解的概念，即針對(duì)某一決策變量無(wú)法找到與之更優(yōu)的解。由于多目標(biāo)優(yōu)化問(wèn)題具有若干個(gè)目標(biāo)，因此通常具有眾多的Pareto最優(yōu)解，并形成Pareto最優(yōu)集。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第11頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(2)調(diào)度問(wèn)題是優(yōu)化問(wèn)題 由于現(xiàn)實(shí)生產(chǎn)生活中

9、優(yōu)化問(wèn)題的復(fù)雜性和多樣化，根據(jù)實(shí)際問(wèn)題建立模型時(shí)約束條件及目標(biāo)函數(shù)中的變量可能是確定型的或不確定型的，因此又可以將優(yōu)化問(wèn)題分為確定型優(yōu)化問(wèn)題和不確定型優(yōu)化問(wèn)題。 對(duì)于不確定型優(yōu)化問(wèn)題，又可大致分為隨機(jī)模型優(yōu)化問(wèn)題和模糊優(yōu)化問(wèn)題等。 另外，根據(jù)解空間的特點(diǎn)還可以將優(yōu)化問(wèn)題分為連續(xù)型優(yōu)化問(wèn)題、離散型優(yōu)化問(wèn)題； 根據(jù)決策變量的特點(diǎn)可以將優(yōu)化問(wèn)題分為線性優(yōu)化問(wèn)題、非線性優(yōu)化問(wèn)題等。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第12頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(3)調(diào)度模型舉例 Pm|Cj問(wèn)題的數(shù)學(xué)模型：,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度

10、2020年7月9日 第13頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(3)調(diào)度模型舉例 相同的問(wèn)題，不同的模型：,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第14頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(3)調(diào)度模型舉例 更多的生產(chǎn)調(diào)度模型見(jiàn)制造工程管理中的優(yōu)化理論與方法2.2節(jié)。 基于分配變量的模型 基于時(shí)間間隔的時(shí)序變量的模型 基于開(kāi)始時(shí)間的時(shí)序變量的模型 更復(fù)雜的調(diào)度模型，可以采用自然語(yǔ)言與數(shù)學(xué)符號(hào)相結(jié)合的方法進(jìn)行描述。舉例(見(jiàn)PDF文檔)。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第15頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(4)優(yōu)化問(wèn)題(模型

11、)的復(fù)雜性 首先看算法的“計(jì)算復(fù)雜性”，通俗說(shuō)來(lái)，就是用計(jì)算機(jī)求解問(wèn)題的難易程度。其度量標(biāo)準(zhǔn)： 一是計(jì)算所需的步數(shù)或指令條數(shù)（這叫時(shí)間復(fù)雜度）； 二是計(jì)算所需的存儲(chǔ)單元數(shù)量（這叫空間復(fù)雜度）。 時(shí)間復(fù)雜度是指在計(jì)算機(jī)科學(xué)與工程領(lǐng)域完成一個(gè)算法所需要的時(shí)間，是衡量一個(gè)算法優(yōu)劣的重要參數(shù)。時(shí)間復(fù)雜度越小，說(shuō)明該算法效率越高，則該算法越有價(jià)值。 時(shí)間復(fù)雜度越來(lái)越受到重視。動(dòng)態(tài)規(guī)劃相關(guān)算法須關(guān)注空間復(fù)雜度。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第16頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(4)優(yōu)化問(wèn)題(模型)的復(fù)雜性 將計(jì)算問(wèn)題按照在不同計(jì)算模型下所需資源的不同予以分

12、類，從而得到一個(gè)對(duì)算法問(wèn)題“難度”的類別，就是復(fù)雜性理論中復(fù)雜性類概念的來(lái)源。 例如一個(gè)問(wèn)題如果在確定性圖靈機(jī)上所需時(shí)間不會(huì)超過(guò)一個(gè)確定的多項(xiàng)式(以輸入的長(zhǎng)度為多項(xiàng)式的不定元)，那么我們稱這類問(wèn)題的集合為P(polynomial time Turing machine)。 而將前述定義中的“確定性圖靈機(jī)”改為“不確定性圖靈機(jī)”，那么所得到的問(wèn)題集合為NP(non-deteministic polynomial time Turing machine)。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第17頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(4)優(yōu)化問(wèn)題(模型)的復(fù)雜

13、性 計(jì)算復(fù)雜性的初衷是理解不同算法問(wèn)題的難度，特別的是一些重要算法問(wèn)題的困難性。為了確切的描述一個(gè)問(wèn)題的困難性，計(jì)算復(fù)雜性的第一步抽象是認(rèn)為多項(xiàng)式時(shí)間是有效的，非多項(xiàng)式時(shí)間是困難的。這基于指數(shù)函數(shù)增長(zhǎng)速度的“違反直覺(jué)”的特性： 如果一個(gè)算法的時(shí)間復(fù)雜性為2n，取輸入的規(guī)模是100，在運(yùn)算速度是每秒1012（關(guān)于CPU速度，參見(jiàn)Instructions per second，其中報(bào)告截止2009年，主流個(gè)人電腦的運(yùn)算速度可以看作是4*1010每秒）的情況下，該程序?qū)?huì)運(yùn)行4*1010年，幾乎是宇宙年齡。 然而多項(xiàng)式的指數(shù)很大的時(shí)候，算法在實(shí)踐中也不能看作是有效的。,李凱(合肥工業(yè)大學(xué)管理學(xué)院)

14、生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第18頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(4)優(yōu)化問(wèn)題(模型)的復(fù)雜性 如果一個(gè)問(wèn)題的復(fù)雜度是該問(wèn)題的一個(gè)實(shí)例規(guī)模n的多項(xiàng)式函數(shù)，則這種可以在多項(xiàng)式時(shí)間內(nèi)解決的問(wèn)題屬于P類問(wèn)題。通俗地稱所有復(fù)雜度為多項(xiàng)式時(shí)間的問(wèn)題為易解的問(wèn)題類，否則為難解的問(wèn)題。 簡(jiǎn)單的說(shuō)，存在多項(xiàng)式時(shí)間的算法的一類問(wèn)題，稱之為P類問(wèn)題；而像梵塔問(wèn)題，推銷員旅行問(wèn)題等問(wèn)題，至今沒(méi)有找到多項(xiàng)式時(shí)間算法解的一類問(wèn)題，稱之為NP問(wèn)題。同時(shí)，P類問(wèn)題是NP問(wèn)題的一個(gè)子集。 多項(xiàng)式時(shí)間問(wèn)題、NP-hard (NP難) 問(wèn)題、強(qiáng)NP-hard問(wèn)題 如果一個(gè)問(wèn)題的特例是NP-hard的，則該問(wèn)題

15、也是NP-hard的。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第19頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(5)常見(jiàn)的NP-難問(wèn)題 背包問(wèn)題： 給定一組物品，每種物品都有自己的重量和價(jià)格，在限定的總重量?jī)?nèi)，我們?nèi)绾芜x擇，才能使得物品的總價(jià)格最高。 設(shè)有一個(gè)容積為b的背包，n個(gè)尺寸分別為ai、價(jià)值為ci的物品，如何裝包使得總價(jià)值最大？(0-1背包問(wèn)題) max 1in cixi s.t. 1inaixi b; xi0,1, i=1,2,n,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第20頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(5)常見(jiàn)的

16、NP-難問(wèn)題 旅行商問(wèn)題： 旅行商問(wèn)題（Traveling Saleman Problem，TSP） 又稱為旅行推銷員問(wèn)題、貨郎擔(dān)問(wèn)題，簡(jiǎn)稱為TSP問(wèn)題，是最基本的路線問(wèn)題，該問(wèn)題是在尋求單一旅行者由起點(diǎn)出發(fā)，通過(guò)所有給定的需求點(diǎn)之后，最后再回到原點(diǎn)的最小路徑成本。 整數(shù)規(guī)劃問(wèn)題；,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第21頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(5)常見(jiàn)的NP-難問(wèn)題 裝箱問(wèn)題： 設(shè)有許多具有同樣結(jié)構(gòu)和負(fù)荷的箱子B1, B2, ，其數(shù)量足夠供所達(dá)到目的之用。每個(gè)箱子的負(fù)荷（可為長(zhǎng)度、重量等等.）為C，今有n個(gè)負(fù)荷為wj，0wjC，j=1,2,

17、n的物品 J1, J2, ,Jn需要裝入箱內(nèi)。裝箱問(wèn)題就是指尋找一種方法，使得能以最小數(shù)量的箱子數(shù)將J1, J2, ,Jn全部裝入箱內(nèi)。 哈密頓回路問(wèn)題： 天文學(xué)家哈密頓(William Hamilton) 提出，在一個(gè)有多個(gè)城市的地圖網(wǎng)絡(luò)中，尋找一條從給定的起點(diǎn)到給定的終點(diǎn)沿 途恰好經(jīng)過(guò)所有其他城市一次的路徑。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第22頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(5)常見(jiàn)的NP-難問(wèn)題 劃分問(wèn)題： 設(shè)有一整數(shù)集合A=a1,a2,an，如何將該集合劃分為兩個(gè)子集A1和A2，使得ajA1 aj= ajA2 aj =(ajA aj)/

18、2。 精確覆蓋問(wèn)題： 在一個(gè)全集X中若干子集的集合為S，精確覆蓋(Exact cover)是指，S的子集S*，滿足X中的每一個(gè)元素在S*中恰好出現(xiàn)一次。即滿足條件： S*中任意兩個(gè)集合沒(méi)有交集，即X中的元素在S*中出現(xiàn)最多一次； S*中集合的全集為X，即X中的元素在S*中出現(xiàn)最少一次。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第23頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(6)優(yōu)化模型的解決思路 多項(xiàng)式時(shí)間問(wèn)題 步驟1.構(gòu)造優(yōu)化模型的多項(xiàng)式時(shí)間最優(yōu)算法； 步驟2.證明上述算法所獲得的解為該模型的最優(yōu)解。 (強(qiáng))NP-hard問(wèn)題 思路1.啟發(fā)式算法(啟發(fā)式規(guī)則、近似

19、算法)； 思路2.精確算法(分枝定界算法、動(dòng)態(tài)規(guī)劃法等)； 思路3.亞啟發(fā)式算法(模擬退火算法、遺傳算法、禁忌搜索算法等)。 啟發(fā)式算法必須針對(duì)具體問(wèn)題特點(diǎn)構(gòu)造相應(yīng)的啟發(fā)式規(guī)則。 精確算法和亞啟發(fā)式算法具有通用框架。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第24頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(7)精確算法 分枝定界算法(B if ( n = 0 ) return 1; else temp= n * Factorial (n-1); return temp; ,規(guī)模減小,RetLoc2,附加內(nèi)容：遞歸,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)

20、調(diào)度 2020年7月9日 第33頁(yè),Page 34,分析,分析：當(dāng)調(diào)用函數(shù)時(shí)，系統(tǒng)為調(diào)用者構(gòu)造一個(gè)由參數(shù)表和返回地址組成的活動(dòng)記錄（工作記錄），并將其壓入工作棧中，當(dāng)有多個(gè)嵌套調(diào)用時(shí)，每調(diào)用一次產(chǎn)生一個(gè)工作記錄，并依次壓入工作棧中。當(dāng)函數(shù)返回時(shí)，彈出棧頂記錄。按照先調(diào)用后返回原則，將工作記錄依次彈出。 對(duì)于遞歸調(diào)用，由于調(diào)用與被調(diào)函數(shù)是同一個(gè)函數(shù)，因此與調(diào)用相關(guān)的概念是“層次”。 工作記錄：,附加內(nèi)容：遞歸,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第34頁(yè),Page 35,分析,計(jì)算Factorial時(shí)活動(dòng)記錄的內(nèi)容：,void main( ) long

21、 x; x=Factorial(4); ,棧頂,RetLoc2,附加內(nèi)容：遞歸,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第35頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(8)亞啟發(fā)式算法 對(duì)于NP-hard問(wèn)題，傳統(tǒng)的精確算法（分枝定界算法、動(dòng)態(tài)規(guī)劃算法等）僅能解決較小規(guī)模的問(wèn)題，這是因?yàn)樗鼈兊目臻g復(fù)雜度或時(shí)間復(fù)雜度隨著問(wèn)題規(guī)模的變大而成指數(shù)型增長(zhǎng)。據(jù)我們了解到的資料，關(guān)于生產(chǎn)調(diào)度中的許多NP-hard問(wèn)題的分枝定界算法很少有能夠處理規(guī)模大于100個(gè)作業(yè)的。 由于計(jì)算機(jī)軟硬件技術(shù)的迅速發(fā)展，促使了局部搜索、模擬退火、可變鄰域搜索、禁忌搜索、遺傳算法等亞啟發(fā)式算法的產(chǎn)生

22、。亞啟發(fā)式算法通常基于搜索技術(shù)，通過(guò)對(duì)優(yōu)化問(wèn)題大規(guī)模解空間中的解搜索和比較，從而獲得質(zhì)量比較好的滿意解。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第36頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(8)亞啟發(fā)式算法 局部搜索(LS, Local Search)： 局部搜索(LS, Local Search)是一種在當(dāng)前可行解的基礎(chǔ)上，按照一定的方法產(chǎn)生鄰域并以該鄰域中的最優(yōu)解作為下一個(gè)當(dāng)前可行解的不斷迭代的搜索算法，當(dāng)算法無(wú)法改進(jìn)某一當(dāng)前可行解時(shí)則算法結(jié)束。對(duì)于優(yōu)化問(wèn)題而言，局部搜索是一種有效的搜索算法。首先，我們可以將一個(gè)優(yōu)化問(wèn)題表述為“對(duì)解向量x的不同參數(shù)尋找一組取

23、值，使得目標(biāo)函數(shù)Z(x)最大化或最小化”。可見(jiàn)其本身就是一個(gè)搜索問(wèn)題，其解空間是參數(shù)的不同組合。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第37頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(8)亞啟發(fā)式算法 局部搜索算法框架： Step 1. 產(chǎn)生一個(gè)初始解x，對(duì)應(yīng)目標(biāo)函數(shù)值Z(x)； Step 2. 在解x的鄰域里找最優(yōu)鄰居x; Step 3. 如果Z(x)Z(x)，則 x=x; Z(x)=Z(x); 轉(zhuǎn)Step 2 ; Step 4. 返回解x和值Z(x)。結(jié)束。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第38頁(yè),第1節(jié)：生產(chǎn)

24、調(diào)度與優(yōu)化,(8)亞啟發(fā)式算法 局部搜索 優(yōu)勢(shì)在于： i)每一次循環(huán)迭代都占有恒定的內(nèi)存需求； ii)它能夠在非常大的解空間中進(jìn)行尋優(yōu)。 缺點(diǎn)在于： i)局部搜索僅能保證獲得局部最優(yōu)解，而無(wú)法斷定該解全局最優(yōu)； ii)解的質(zhì)量可能會(huì)由于初始解的不同有一定的擾動(dòng)。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第39頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(8)亞啟發(fā)式算法 模擬退火(SA, Simulated Annealing)： 模擬退火是對(duì)局部搜索算法的一種拓展。 從某種意義上看，局部搜索之所以陷入局部最優(yōu)陷阱是因?yàn)樗看蔚偸沁x擇當(dāng)前解鄰域中的局部最優(yōu)解。然而事

25、實(shí)上，一個(gè)全局最優(yōu)解未必在某一當(dāng)前局部最優(yōu)解的鄰域中。 模擬退火算法的思想是每次迭代算法以一定的概率接受劣解而不是永遠(yuǎn)選擇鄰域中的局部最優(yōu)解。為了能使算法最終向全局最優(yōu)解收斂，接受劣解的概率隨迭代步數(shù)的增加而變小直至接近于0。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第40頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(8)亞啟發(fā)式算法 模擬退火(SA, Simulated Annealing)： 模擬退火算法最早由Metropolis提出，并進(jìn)而廣泛用于解決大規(guī)模的復(fù)雜問(wèn)題。模擬退火是算法思想來(lái)源于現(xiàn)實(shí)生活中金屬物體的退火過(guò)程并因此稱之為模擬退火。當(dāng)金屬物體溫度比較高的

26、時(shí)候，分子運(yùn)動(dòng)比較劇烈，分子排列具有很大的隨意性，此時(shí)物體具有比較高的能量級(jí)別；而當(dāng)溫度降低，分子運(yùn)動(dòng)變得緩慢并最終趨于穩(wěn)定構(gòu)成正方體的晶體矩陣，而此時(shí)物體的能量級(jí)別也達(dá)到最低。同樣在模擬退火算法中，溫度比較高時(shí)算法接受劣解的可能性比較大，溫度較低時(shí)接受劣解的概率減小并最終趨于0，從而使得算法結(jié)束時(shí)優(yōu)化問(wèn)題的目標(biāo)函數(shù)趨于最優(yōu)。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第41頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(8)亞啟發(fā)式算法 模擬退火算法框架： Step 1. 產(chǎn)生一個(gè)初始解x, 最優(yōu)解x*=x；k=0; tk=tmax; Step 2. 若在該溫度達(dá)到內(nèi)循環(huán)

27、停止條件, 則轉(zhuǎn)Step 3; 否則, 從鄰域N(x)中隨機(jī)選擇一個(gè)解y ; 計(jì)算Z=Z(y)-Z(x); 若Z 0，則x*=y; 否則, 若exp(- Z/tk)random(0,1),則x*=y; 重復(fù)Step 2. Step 3. tk+1=d(tk); k=k+1; 若滿足停止條件, 則返回解x和值Z(x), 結(jié)束。否則, 轉(zhuǎn)Step 2.,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第42頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(8)亞啟發(fā)式算法 可變鄰域搜索(VNS, Variable Neighborhood Search)： 其原理是通過(guò)在搜索過(guò)程中不斷

28、改變鄰域結(jié)構(gòu)而使得滿意解不會(huì)陷入局部最優(yōu)的陷阱。它也是對(duì)局部搜索的一種擴(kuò)展，然而它與模擬退火算法避免陷入局部最優(yōu)陷阱的機(jī)制卻完全不同?？勺冟徲蛩阉髡J(rèn)為局部搜索之所以陷入局部最優(yōu)是因?yàn)槠溧徲驑?gòu)造方式不恰當(dāng)并且僅采用一種鄰域生成方法，因此要想獲得全局最優(yōu)解可以設(shè)計(jì)許多替補(bǔ)鄰域生成方式，當(dāng)?shù)谝环N鄰域生成方式陷入局部最優(yōu)，可以轉(zhuǎn)而采用第二種鄰域生成方式改變搜索空間，直至采用所用的鄰域生成方式均無(wú)法獲得更優(yōu)的解則算法結(jié)束。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第43頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(8)亞啟發(fā)式算法 可變鄰域搜索算法框架： 初始化: 設(shè)計(jì)一系列鄰域

29、生成方法Nk(k=1,2,kmax);構(gòu)造初始可行解x和結(jié)束條件； 當(dāng)結(jié)束條件不滿足, 循環(huán)如下步驟： I) k=1; II) 循環(huán)如下步驟，直到k=kmax; i)在x的第k個(gè)鄰域中Nk隨機(jī)生成一個(gè)鄰居x; ii)尋找x鄰域中的局部最優(yōu)解x; iii)如果x優(yōu)于x, 則x=x;k=1;繼續(xù)在Nk中搜索, 否則k=k+1.,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第44頁(yè),第1節(jié)：生產(chǎn)調(diào)度與優(yōu)化,(8)亞啟發(fā)式算法 可變鄰域搜索較常用變形VND： 初始化: 設(shè)計(jì)一系列鄰域生成方法Nk(k=1,2,kmax);構(gòu)造初始可行解x和結(jié)束條件； 當(dāng)結(jié)束條件不滿足

30、, 循環(huán)如下步驟： I) k=1; II) 循環(huán)如下步驟，直到k=kmax; i)在x的第k個(gè)鄰域Nk中尋找局部最優(yōu)解x; ii)如果x優(yōu)于x, 則x=x ; 否則k=k+1.,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第45頁(yè),第2節(jié)：生產(chǎn)調(diào)度問(wèn)題的符號(hào)表示與分類,(1)三參數(shù)表示法簡(jiǎn)介 自從1954年Johnson發(fā)表第一篇關(guān)于調(diào)度問(wèn)題的研究文獻(xiàn)以來(lái)，人們對(duì)調(diào)度問(wèn)題產(chǎn)生了濃厚的興趣。 相同的調(diào)度問(wèn)題由于研究時(shí)間或研究人員所在研究領(lǐng)域的不同可能有不同的稱謂，例如： 對(duì)于作業(yè)的到達(dá)時(shí)間，早期的文獻(xiàn)一般稱為準(zhǔn)備時(shí)間(ready time)，而近期文獻(xiàn)一般稱為

31、釋放時(shí)間(release date)；對(duì)于機(jī)器速度相同的平行機(jī)問(wèn)題，排序引論稱為同速機(jī)問(wèn)題，而現(xiàn)代排序論稱為同型機(jī)問(wèn)題；對(duì)于機(jī)器速度不同且差異恒定的平行機(jī)問(wèn)題，排序引論稱為恒速機(jī)問(wèn)題，而現(xiàn)代排序論稱為同類機(jī)問(wèn)題。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第46頁(yè),第2節(jié)：生產(chǎn)調(diào)度問(wèn)題的符號(hào)表示與分類,(1)三參數(shù)表示法簡(jiǎn)介 現(xiàn)實(shí)中生產(chǎn)過(guò)程的復(fù)雜性造成了不同調(diào)度問(wèn)題的約束條件與目標(biāo)函數(shù)有很大差異。Graham提出的 三參數(shù)表示法能夠較簡(jiǎn)單且清晰地描述一個(gè)具體的調(diào)度問(wèn)題，并逐漸成為人們表示調(diào)度問(wèn)題的標(biāo)準(zhǔn)形式。其中， 域用來(lái)表示與機(jī)器相關(guān)的一些信息； 域用于表

32、示與作業(yè)相關(guān)的一些信息； 域指示調(diào)度問(wèn)題所要達(dá)到的目標(biāo)。 例如，可以用符號(hào)Qm|rj|Cj來(lái)表示作業(yè)到達(dá)時(shí)間(釋放時(shí)間)不同、目標(biāo)是最小化完工時(shí)間和的同類機(jī)調(diào)度問(wèn)題，其中，Qm表示同類機(jī)調(diào)度類型，rj表示作業(yè)具有到達(dá)時(shí)間(release date)的約束，Cj表示調(diào)度的目標(biāo)是最小化完工時(shí)間和。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第47頁(yè),第2節(jié)：生產(chǎn)調(diào)度問(wèn)題的符號(hào)表示與分類,(2)三參數(shù)表示法調(diào)度問(wèn)題分類 根據(jù)域進(jìn)行分類，可以將調(diào)度問(wèn)題劃分為單機(jī)問(wèn)題、串行調(diào)度問(wèn)題、并行調(diào)度問(wèn)題以及混合調(diào)度問(wèn)題。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生

33、產(chǎn)調(diào)度 2020年7月9日 第48頁(yè),第2節(jié)：生產(chǎn)調(diào)度問(wèn)題的符號(hào)表示與分類,(2)三參數(shù)表示法調(diào)度問(wèn)題分類 根據(jù)域中調(diào)度前所給作業(yè)信息的多少，可以將調(diào)度問(wèn)題分為離線問(wèn)題、在線問(wèn)題。離線問(wèn)題就是確定性的調(diào)度問(wèn)題，即在調(diào)度之前已知作業(yè)的所有相關(guān)信息；在在線問(wèn)題中，僅知道已到達(dá)作業(yè)的確切信息，而對(duì)尚未到達(dá)的作業(yè)一無(wú)所知。 域中常見(jiàn)的符號(hào)有：rj表示作業(yè)具有不同的到達(dá)時(shí)間；pmtn表示作業(yè)可以中斷；prec表示作業(yè)有先后次序的限制；STsi表示作業(yè)之間有setup時(shí)間，但此setup時(shí)間與作業(yè)調(diào)度次序無(wú)關(guān)；STsd表示作業(yè)之間有setup時(shí)間，而且此setup時(shí)間與作業(yè)調(diào)度次序有關(guān)；Mj表示某些作業(yè)具

34、有可加工機(jī)器結(jié)合，而不能夠在此集合之外的機(jī)器上加工。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第49頁(yè),第2節(jié)：生產(chǎn)調(diào)度問(wèn)題的符號(hào)表示與分類,(2)三參數(shù)表示法調(diào)度問(wèn)題分類 三參數(shù)表示法中的域用于指示調(diào)度的目標(biāo)。 正則目標(biāo)(Regular Performance Measures)和非正則目標(biāo)。正則目標(biāo)是指目標(biāo)函數(shù)是作業(yè)完工時(shí)間的非減函數(shù)，而非正則目標(biāo)則未必。常見(jiàn)的正則目標(biāo)有：Cmax表示調(diào)度目標(biāo)是最小化最大完工時(shí)間；Cj表示最小化完工時(shí)間和；wjCj表示最小化加權(quán)完工時(shí)間和；Lmax表示最小化最大延遲時(shí)間；Tj表示最小化延遲時(shí)間和；wjTj表示最小化加

35、權(quán)延遲時(shí)間和；Uj表示最小化誤工作業(yè)個(gè)數(shù)；wjUj表示最小化加權(quán)誤工作業(yè)個(gè)數(shù)。最常見(jiàn)的兩個(gè)非正則目標(biāo)是(Ej+Tj)和(wjEj+wjTj)，分別表示最小化提前/延遲時(shí)間和、最小化加權(quán)提前/延遲時(shí)間和，這兩類調(diào)度問(wèn)題研究的是及時(shí)交付的調(diào)度問(wèn)題。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第50頁(yè),第3節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)題及其啟發(fā)式規(guī)則,(1)常見(jiàn)調(diào)度參數(shù)回顧(作業(yè)信息中) 加工時(shí)間(Processing time)(pj) ： The amount of processing required by job j 釋放時(shí)間(Release date) (rj

36、)： The time at which job j is available for processing 預(yù)交付時(shí)間(Due date) (dj)： The time at which the processing of job j is due to be completed,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第51頁(yè),第3節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)題及其啟發(fā)式規(guī)則,(1)常見(jiàn)調(diào)度參數(shù)回顧(目標(biāo)函數(shù)中) 完工時(shí)間(Completion time)(Cj): The time at which the processing of job j is fi

37、nished 工作流時(shí)間(Flowtime)(Fj): The time job j spends in the system: Fj = Cj rj 延遲時(shí)間(Lateness)(Lj): The amount of time by which the completion time of job j exceeds its due date: Lj = Cj dj 延遲時(shí)間(Tardiness)(Tj): The lateness of job j if it fails to meet its due date, or zero otherwise: Tj = max0, Lj,李凱(合

38、肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第52頁(yè),第3節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)題及其啟發(fā)式規(guī)則,(2)常見(jiàn)目標(biāo)函數(shù),李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第53頁(yè),第3節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)題及其啟發(fā)式規(guī)則,(3)常見(jiàn)調(diào)度問(wèn)題復(fù)雜性：多項(xiàng)式時(shí)間問(wèn)題,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第54頁(yè),第3節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)題及其啟發(fā)式規(guī)則,(3)常見(jiàn)調(diào)度問(wèn)題復(fù)雜性：多項(xiàng)式時(shí)間問(wèn)題,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第55頁(yè),第3節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)題

39、及其啟發(fā)式規(guī)則,(3)常見(jiàn)調(diào)度問(wèn)題復(fù)雜性：多項(xiàng)式時(shí)間問(wèn)題,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第56頁(yè),第3節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)題及其啟發(fā)式規(guī)則,(3)常見(jiàn)調(diào)度問(wèn)題復(fù)雜性：NP-hard問(wèn)題,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第57頁(yè),第3節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)題及其啟發(fā)式規(guī)則,(3)常見(jiàn)調(diào)度問(wèn)題復(fù)雜性：NP-hard問(wèn)題,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第58頁(yè),第3節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)題及其啟發(fā)式規(guī)則,(3)常見(jiàn)調(diào)度問(wèn)題復(fù)雜性：NP-hard問(wèn)題,李凱(合肥工業(yè)

40、大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第59頁(yè),第3節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)題及其啟發(fā)式規(guī)則,(4)常見(jiàn)調(diào)度啟發(fā)式規(guī)則 WSPT規(guī)則能夠獲得1|wjCj問(wèn)題最優(yōu)解。 WSPT(Weighted Shortest Processing Time first, 加權(quán)最短加工時(shí)間最短)。Total weighted flowtime (completion time) is minimized by SWPT sequencing (p1/w1 p2/w2 . . . pn/wn).,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第60頁(yè),第3

41、節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)題及其啟發(fā)式規(guī)則,(4)常見(jiàn)調(diào)度啟發(fā)式規(guī)則 SPT規(guī)則能夠獲得1|Cj問(wèn)題最優(yōu)解。 Smallest-Processing-Time (SPT) Rule. Whenever a machine is free for assignment, assign that job with the smallest processing time among all unassigned jobs. SPT規(guī)則能夠獲得Pm|Cj問(wèn)題最優(yōu)解。 例：3個(gè)機(jī)器，如下10個(gè)作業(yè),李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第61頁(yè),第3節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)

42、題及其啟發(fā)式規(guī)則,(4)常見(jiàn)調(diào)度啟發(fā)式規(guī)則 SRPT規(guī)則能夠獲得Pm|pmtn|Cj問(wèn)題最優(yōu)解。 Bakers Rule. At any moment of time, schedule that ready job with the smallest remaining processing time. 例： ERD規(guī)則能夠獲得1|rj|Cmax問(wèn)題最優(yōu)解。 ERD: Earliest Release Date first. (先來(lái)先服務(wù)),李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第62頁(yè),第3節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)題及其啟發(fā)式規(guī)則,(4)常見(jiàn)調(diào)度啟發(fā)式規(guī)

43、則 EDD規(guī)則能夠獲得1|Lmax問(wèn)題、 1|rj,pj=1|Lmax問(wèn)題最優(yōu)解。 EDD: Earliest Due Date first. Step 1. 在當(dāng)前到達(dá)的任務(wù)中，選取工期最小者加工（若有多個(gè)，任選其一）； Step 2. 每當(dāng)加工完某任務(wù)，則轉(zhuǎn)Step 1，重新確定當(dāng)前加工任務(wù)，直到加工完全部任務(wù)。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第63頁(yè),第3節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)題及其啟發(fā)式規(guī)則,(4)常見(jiàn)調(diào)度啟發(fā)式規(guī)則 可中斷的EDD規(guī)則能夠獲得1|rj,pmtn|Lmax問(wèn)題最優(yōu)解。 At any moment of time, sched

44、ule the job with the earliest due date.,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第64頁(yè),第3節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)題及其啟發(fā)式規(guī)則,(4)常見(jiàn)調(diào)度啟發(fā)式規(guī)則 大尾優(yōu)先規(guī)則能夠獲得1|qj|Cmax問(wèn)題最優(yōu)解。 1|qj|Cmax問(wèn)題等價(jià)于1|Lmax問(wèn)題。 LDT: Largest Delivery Time first.,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第65頁(yè),第3節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)題及其啟發(fā)式規(guī)則,(4)常見(jiàn)調(diào)度啟發(fā)式規(guī)則 McNaughtons Wrap-Aro

45、und規(guī)則可以獲得Pm|pmtn|Cmax問(wèn)題最優(yōu)解。 D=Cmax=maxpmax, (pj)/m McNaughtons Rule：Compute D. Assign the jobs in any order from time 0 until time D on machine 1. If a jobs processing extends beyond time D, preempt the job at time D, and compute its processing on machine 2, starting at time 0. Repeat this process u

46、ntil all jobs are assigned. (例如，兩個(gè)機(jī)器，作業(yè)信息如下：),李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第66頁(yè),第3節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)題及其啟發(fā)式規(guī)則,(4)常見(jiàn)調(diào)度啟發(fā)式規(guī)則 Modified McNaughton規(guī)則可以獲得Pm|pmtn|Cmax問(wèn)題、 Pm|rj,pmtn|Cmax問(wèn)題及其對(duì)應(yīng)Online情形問(wèn)題的最優(yōu)解。 考慮了超長(zhǎng)作業(yè)的調(diào)度 D=Cmax=maxpmax, (pj)/m Modified McNauthtons Rule：If pmax(pj)/m, then schedule the jobs

47、by McNaughtons wrap-around rule; otherwise schedule the longest job on one machine and delete the jobs from job set. (例如，兩個(gè)機(jī)器，作業(yè)信息如下：),李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第67頁(yè),第3節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)題及其啟發(fā)式規(guī)則,(4)常見(jiàn)調(diào)度啟發(fā)式規(guī)則 SRPT-FM規(guī)則可以獲得Qm|pmtn|Cj問(wèn)題最優(yōu)解。 SRPT-FM: Shortest Remaining Processing Time on the Fastes

48、t Machine rule.,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第68頁(yè),第3節(jié)：常見(jiàn)生產(chǎn)調(diào)度問(wèn)題及其啟發(fā)式規(guī)則,(4)常見(jiàn)調(diào)度啟發(fā)式規(guī)則 P2|Cmax問(wèn)題是NP-hard的。LPT規(guī)則的解收斂到Pm|Cmax問(wèn)題最優(yōu)解的(4/3-1/3m)倍以內(nèi)。 例：m=3,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第69頁(yè),第4節(jié)：生產(chǎn)調(diào)度問(wèn)題求解舉例,(1)啟發(fā)式規(guī)則構(gòu)建舉例 Qm|qj|Cmax問(wèn)題的LPDT算法 Koulamas & Kyparisis (Scheduling on uniform parall

49、el machines to minimize maximum Lateness, Operations Research Letters, 2000,26:175-179.)論證了LDT(大尾優(yōu)先)算法是(m-1)smax/si+1-近似算法。 例題：考慮2個(gè)均有11個(gè)機(jī)器的Qm|qj|Cmax問(wèn)題。 問(wèn)題1. s1=s2=s11=10。最壞誤差界：1.91。 問(wèn)題2. s1=10, s2=s3=s11=1。最壞誤差界：6。 定理：假設(shè)在時(shí)刻，僅考慮作業(yè)J1和J2，p1+q1p2+q2，機(jī)器M1和M2均空閑，令s2=1，s1=k1。則： Cmax(J1M1,J2M2)Cmax(J1M2,J2

50、M1)。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第70頁(yè),第4節(jié)：生產(chǎn)調(diào)度問(wèn)題求解舉例,(1)啟發(fā)式規(guī)則構(gòu)建舉例 Qm|qj|Cmax問(wèn)題的LPDT算法 Step 1. 機(jī)器按照速度從大到小排列，各機(jī)器調(diào)度隊(duì)列置空將作業(yè)隊(duì)列中；所有作業(yè)按照長(zhǎng)度與尾時(shí)間之和非增排序。 Step 2. 考慮作業(yè)隊(duì)列隊(duì)首作業(yè)，按照LDT規(guī)則預(yù)插入各機(jī)器子調(diào)度隊(duì)列，指定Cmax最小的機(jī)器加工此作業(yè)(如果存在多個(gè)Cmax最小的機(jī)器，則現(xiàn)在慢機(jī)器)，將此作業(yè)從作業(yè)隊(duì)列中刪除。 Step 3. 如果作業(yè)隊(duì)列空，結(jié)束；否則，轉(zhuǎn)Step 2。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理

51、第5章：生產(chǎn)調(diào)度 2020年7月9日 第71頁(yè),第4節(jié)：生產(chǎn)調(diào)度問(wèn)題求解舉例,(1)啟發(fā)式規(guī)則構(gòu)建舉例 Qm|qj|Cmax問(wèn)題的LPDT算法 例：考慮如下 Qm|qj|Cmax 問(wèn)題：有2個(gè)機(jī)器，s1=2，s2=1；3個(gè)作業(yè)長(zhǎng)度分別為1、4、6，尾時(shí)間分別為3、2、1；則LDT調(diào)度結(jié)果Cmax=6.5，見(jiàn)圖1-a；LPDT調(diào)度結(jié)果Cmax=6，見(jiàn)圖1-b。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第72頁(yè),第4節(jié)：生產(chǎn)調(diào)度問(wèn)題求解舉例,(1)啟發(fā)式規(guī)則構(gòu)建舉例 Qm|qj|Cmax問(wèn)題的LPDT算法說(shuō)明： I) LPDT算法仍然不能保證求得問(wèn)題的最優(yōu)解

52、。 II) 通過(guò)LPDT排序并依次為作業(yè)指定機(jī)器，通常能夠獲得較好的解，見(jiàn)例。這是因?yàn)長(zhǎng)DT沒(méi)有考慮到作業(yè)長(zhǎng)度對(duì)調(diào)度結(jié)果的影響，特別是在機(jī)器速度有差別的同類機(jī)情形會(huì)降低調(diào)度結(jié)果的質(zhì)量。 III) 將作業(yè)按照加工時(shí)間與尾時(shí)間之和非增排序可能會(huì)使得某些尾時(shí)間較大的作業(yè)考慮的時(shí)間較后，而且LDT能夠使得問(wèn)題中各機(jī)器調(diào)度隊(duì)列排序最優(yōu)，所以單純使用LPDT規(guī)則未必能夠保證各機(jī)器調(diào)度隊(duì)列最優(yōu)。在步驟2中，我們將某作業(yè)按照LDT規(guī)則預(yù)插入機(jī)器調(diào)度隊(duì)列中，能夠保證各機(jī)器調(diào)度隊(duì)列最優(yōu)。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第73頁(yè),第4節(jié)：生產(chǎn)調(diào)度問(wèn)題求解舉例,(1)

53、啟發(fā)式規(guī)則構(gòu)建舉例 Qm|qj|Cmax問(wèn)題的 LPDT算法 令： LB1為對(duì)應(yīng)單機(jī)LDT值； LB2=max1jn(pj/s1+qj)。 LB=max(LB1,LB2)。,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第74頁(yè),(1)啟發(fā)式規(guī)則構(gòu)建舉例 Qm|rj|Cj問(wèn)題的HRS算法 （在提出此算法之前自己發(fā)表了相關(guān)論文，但結(jié)論不夠完美！） 關(guān)于SPT和ERD無(wú)法使得Qm|rj|Cj問(wèn)題獲得比較好的解的思考： I) 當(dāng)前作業(yè)后面會(huì)有多少作業(yè)？很難確定。 II)在同類機(jī)問(wèn)題中一般假定s1 s2 sm，即優(yōu)先考慮處理能力強(qiáng)的機(jī)器。將2個(gè)作業(yè)同時(shí)調(diào)度到不同機(jī)器上

54、時(shí)，應(yīng)將長(zhǎng)作業(yè)調(diào)度到速度快的機(jī)器，將短作業(yè)調(diào)度到速度慢的機(jī)器。 III) 另外，考慮2個(gè)等長(zhǎng)但釋放時(shí)間不同的作業(yè)調(diào)度到2個(gè)機(jī)器上，應(yīng)將后釋放的作業(yè)調(diào)度到速度快的機(jī)器上方能得到較好的調(diào)度結(jié)果。,第4節(jié)：生產(chǎn)調(diào)度問(wèn)題求解舉例,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第75頁(yè),(1)啟發(fā)式規(guī)則構(gòu)建舉例 Qm|rj|Cj問(wèn)題的HRS算法 Step 1. 將作業(yè)隊(duì)列中所有作業(yè)按照LPT-LRD排序，即長(zhǎng)作業(yè)優(yōu)先，長(zhǎng)度相同的作業(yè)后到達(dá)優(yōu)先；各機(jī)器調(diào)度隊(duì)列為空集； Step 2. 考慮作業(yè)隊(duì)列首作業(yè)，將之預(yù)插入各機(jī)器調(diào)度隊(duì)列，預(yù)插入時(shí)根據(jù)作業(yè)到達(dá)時(shí)間近可能靠近調(diào)度隊(duì)列

55、的首部；選擇完成時(shí)間和變化最小調(diào)度隊(duì)列對(duì)應(yīng)的機(jī)器加工此作業(yè)；將此作業(yè)從作業(yè)隊(duì)列中刪除； Step 3. 如果作業(yè)隊(duì)列空，則結(jié)束；否則，轉(zhuǎn)Step 2。,第4節(jié)：生產(chǎn)調(diào)度問(wèn)題求解舉例,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第76頁(yè),(1)啟發(fā)式規(guī)則構(gòu)建舉例 Qm|rj|Cj問(wèn)題的HRS算法 說(shuō)明： I) HRS算法仍然不能保證求得問(wèn)題的最優(yōu)解，這是因?yàn)镼m|rj|Cj問(wèn)題是強(qiáng)NP-hard問(wèn)題，不可能存在多項(xiàng)式時(shí)間的最優(yōu)算法； II) 通過(guò)LPT-LRD排序并依次為作業(yè)指定機(jī)器，使得為作業(yè)指定機(jī)器的過(guò)程中滿足LPT和LRD規(guī)則； III) HRS算法優(yōu)先

56、考慮長(zhǎng)作業(yè)和后釋放作業(yè)，但將作業(yè)預(yù)插入各機(jī)器調(diào)度隊(duì)列中時(shí)盡量將其插到已考慮過(guò)作業(yè)的前面，因此，對(duì)于各機(jī)器上的調(diào)度隊(duì)列仍然盡量滿足SPT和ERD規(guī)則；,第4節(jié)：生產(chǎn)調(diào)度問(wèn)題求解舉例,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第77頁(yè),(1)啟發(fā)式規(guī)則構(gòu)建舉例 Qm|rj|Cj問(wèn)題的HRS算法 說(shuō)明： IV) 由于所有作業(yè)按照LPT-LRD排序，因此相對(duì)于先考慮的作業(yè)，對(duì)于任意機(jī)器上的調(diào)度隊(duì)列，尚未考慮的作業(yè)應(yīng)具有更高的優(yōu)先級(jí)。這樣，在預(yù)插入一個(gè)作業(yè)時(shí)，能夠較準(zhǔn)確地計(jì)算出其對(duì)其后續(xù)作業(yè)完成時(shí)間及完成時(shí)間和的影響,第4節(jié)：生產(chǎn)調(diào)度問(wèn)題求解舉例,李凱(合肥工業(yè)大學(xué)

57、管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第78頁(yè),(1)啟發(fā)式規(guī)則構(gòu)建舉例 Qm|rj|Cj問(wèn)題的HRS算法,第4節(jié)：生產(chǎn)調(diào)度問(wèn)題求解舉例,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第79頁(yè),(2)亞啟發(fā)式算法構(gòu)建舉例 Pm|Cmax問(wèn)題的模擬退火算法 Pm|Cmax問(wèn)題是一類常見(jiàn)的平行機(jī)調(diào)度問(wèn)題，受到廣大研究學(xué)者的關(guān)注。早期的文獻(xiàn)一般基于一些啟發(fā)式規(guī)則或加以改進(jìn)。例如，Graham首先將LPT(Longest Processing Time first)規(guī)則應(yīng)用到此問(wèn)題；Coffman et al.根據(jù)裝箱問(wèn)題與最大完工時(shí)間問(wèn)題的關(guān)

58、系，為Pm|Cmax問(wèn)題提出了著名的MULTIFIT算法。雖然MULTIFIT算法不能保證嚴(yán)格優(yōu)于LPT算法，但Friesen和Yue均證明了其最壞誤差界優(yōu)于LPT。另外一些算法則基于LPT或MULTIFIT進(jìn)行改進(jìn)以求得更高質(zhì)量的解。 Lee W-C., Wu C-C., Chen P. A simulated annealing approach to makespan minimization on identical parallel machines. International Journal of Advanced Manufacturing Technology, 2006, 31:328-334,第4節(jié)：生產(chǎn)調(diào)度問(wèn)題求解舉例,李凱(合肥工業(yè)大學(xué)管理學(xué)院) 生產(chǎn)運(yùn)作管理第5章：生產(chǎn)調(diào)度 2020年7月9日 第80頁(yè),(2)亞啟發(fā)式算法構(gòu)建舉例 Pm|Cmax問(wèn)題的模擬退火算法 SA-LWC算法的性能優(yōu)于過(guò)去的啟發(fā)式算法，然而，我們認(rèn)為它存在著一些不足之處，其中最主要的是： SA-LWC算法僅采用交換鄰域一種鄰域生成方法，即交換不同處理機(jī)