【摘要】：本文主要研究的是帶有加工機器約束的平行機在線排序問題。在此問題中,每個工件都對應一個到達時間rj,一個加工時間pj和一個加工機器集合Mj,工件只能在時刻rj之后被安排到Mj中的某個機器上加工,加工需要占用pj個單位時間。我們考慮這個問題的在線情形。也就是說,只有在此工件到達之后,我們才能得到這個工件的完整信息,甚至包括它是否存在。而在此工件到達后,我們可以選擇立刻安排它,或者將此工件推遲到之后的某個時間再進行安排。我們的目標是最小化時間表長。我們考慮的是此問題的四種特殊情形:嵌套加工機器集合、包含加工機器集合、樹型加工機器集合以及區(qū)間加工機器集合。在第二章,我們考慮的是嵌套加工機器集合的情形。在我們的問題中,機器數(shù)目是任意的且工件都帶有相同的加工時間。對于此問題,我們給出算法H1,在此算法中,我們將工件安排在時刻αp+kp(α=(?)/2,k= 0,1,2,...)加工,并且在任意時刻,我們優(yōu)先安排帶有最小|Mj|的工件。算法H1的競爭比為(?)/2并且此算法是該問題的最優(yōu)在線算法。在第三章,我們考慮的是包含加工機器集合的情形。首先我們考慮的問題是所有工件帶有相同的加工時間且機器數(shù)是任意的。對于此問題,我們給出算法H2。H2與H1較為類似,不同的是我們不僅將工件安排在αp+kp時刻加工,還將工件安排在2αp + kp時刻加工,其中α =(?)-1,k= 0,1,2,...。我們證明了算法H2的競爭比為(?)并且它是此問題的最優(yōu)在線算法。之后我們考慮的問題是機器數(shù)為2且工件的加工時間是任意的。同樣我們給出了此問題的最優(yōu)在線算法。在第四章,我們考慮的是樹型加工機器集合。首先我們考慮的是機器數(shù)為3且工件的加工時間為任意的情形。我們證明了此問題的下界為3/2,并給出了此問題的最優(yōu)在線算法。之后,我們考慮了樹型圖的一種特殊情形:星型圖。我們考慮的是機器數(shù)為任意且工件都帶有相同加工時間的情形。我們證明了此問題的下界為(?)并給出了此問題的最優(yōu)在線算法。在第五章,我們考慮的是區(qū)間加工集合的情形。在我們考慮的問題中,工件的加工時間都相同且只有兩種不同的加工機器集合。我們給出了此問題的下界為3/2,并給出了此問題的最優(yōu)在線算法。
【學位授予單位】：華東理工大學
【學位級別】：博士
【學位授予年份】：2018
【分類號】：O223
【圖文】：

中的每一個結點代表一臺機器，每一個工件都對應一個結點，并且此工件所對逡逑應的結點到根節(jié)點的唯一的路上的所有結點（也就是機器）所組成的機器集合逡逑就是該工件的加工機器集合。圖１．１就是一種樹形加工機器集合的情形，其中工逡逑件九Ｊ２，邋Ｊ３，邋Ｊ４分別對應的是機器結點Ｍ２，邋Ａｆ２，邋Ｍ３，邋Ａｆ６，那么它們的加工機器集合分別逡逑為＝邋＿Ｍ２邋＝邋｛`e，鳩｝，＝邋｛Ｍ１；邋Ｍ２，邋Ｍ３｝，＝邋｛Ｍｌ邋Ｍ５，邋Ａｆ６｝。逡逑在區(qū)間加工機器集合情形中，所有的機器按某個順序排序為．．，ＡＵ，任逡逑意的工件，？對應到兩個機器的下標％和６＾％邋Ｓ邋￣），則由機器ｉｌｆｙ，Ｍｔ＋１，Ｍ￣＋２，．．．，逡逑組成的機器集合即為工件七的加工機器集合。例如我們現(xiàn)在有四個機器Ａｔ邋Ａｆ２，邋ｉｌ／３，邋ｉ＼／４逡逑和三個工件九九邋Ｊ３，且刈１邋＝邐＝邋｛ＡＪ２，Ｍ３｝，Ｍ３邋＝邋｛ｉ＼／２，Ｍｉ，Ｍ４｝，逡逑則此情形是區(qū)間加工機器集合情形。逡逑顯然

【參考文獻】

相關期刊論文 前2條

1 周萍;蔣義偉;何勇;;有兩個服務等級的平行機排序問題[J];高校應用數(shù)學學報A輯;2007年03期

2 ;A CLASS OF GENERALIZED MULTIPROCESSOR SCHEDULING PROBLEMS[J];Systems Science and Mathematical Sciences;2000年04期

本文編號：2774085