對(duì)任務(wù)安排、服務(wù)提供和零件加工等過(guò)程進(jìn)行排序優(yōu)化的調(diào)度理論,在管理決策領(lǐng)域存在著大量的應(yīng)用,能產(chǎn)生巨大的社會(huì)經(jīng)濟(jì)效益。經(jīng)典調(diào)度理論中總是假設(shè)工件參數(shù)是固定不變的,而且機(jī)器在整個(gè)調(diào)度周期內(nèi)的運(yùn)行狀態(tài)也不會(huì)發(fā)生改變。但管理決策者目前面臨的復(fù)雜生產(chǎn)過(guò)程和客戶多樣化的需求,使得調(diào)度優(yōu)化問(wèn)題的研究對(duì)象也相應(yīng)的發(fā)生變化。工件的時(shí)間參量可以發(fā)生改變,機(jī)器運(yùn)行也可能需要中斷一段時(shí)間來(lái)進(jìn)行諸如保養(yǎng)維護(hù)、工具更換、效率調(diào)整等活動(dòng)。而此時(shí)工件/機(jī)器參數(shù)往往是可控的,針對(duì)這一新的變化,本文主要研究含可控時(shí)間參量的生產(chǎn)調(diào)度問(wèn)題及相應(yīng)的優(yōu)化算法。首先,本文研究了帶資源依賴的釋放時(shí)間的單機(jī)調(diào)度問(wèn)題。每一工件一旦釋放即開始進(jìn)行加工,其釋放時(shí)間與假定的初始釋放時(shí)間存在偏差即會(huì)產(chǎn)生釋放成本。需要確定工件序列和所有工件的釋放時(shí)間,使得釋放成本、時(shí)間表長(zhǎng)和總完工時(shí)間的加權(quán)和總成本目標(biāo)函數(shù)最小�？紤]了兩種情形:情形一是初始釋放時(shí)間是限制性的,它是NP難問(wèn)題;另一情形是初始釋放時(shí)間為非限制性的,它是多項(xiàng)式時(shí)間可解問(wèn)題,時(shí)間復(fù)雜度為O（n log n）。其次,基于實(shí)際應(yīng)用中出現(xiàn)的涉及可控且可變加工時(shí)間的調(diào)度問(wèn)題,本文研究了含資源依... 

【文章來(lái)源】：東南大學(xué)江蘇省211工程院校985工程院校教育部直屬院校

【文章頁(yè)數(shù)】：148 頁(yè)

【學(xué)位級(jí)別】：博士

【部分圖文】：

圖１．１：論文框架結(jié)構(gòu)??１６??

釋放時(shí)間ｂ的資源消費(fèi)函數(shù)為??ｆ（ｒｊ）?＝?ａ?ｍａｘ｛ｗ?—?ｒｊ，?０｝?＋?＾?ｍａｘ｛ｒｊ?—?ｔ；，?０｝，??其中ａ、／３分別為工件提前和延后釋放的單位成本。資源消費(fèi)函數(shù)／＆）是如圖２．１（ｂ）所??示的Ｖ－型。而大部分涉及帶資源依賴的釋放時(shí)間的文獻(xiàn)中，釋放時(shí)間的資源消費(fèi)函數(shù)是??ｆ（ｒｊ）?＝?ｏ－ｍａｘ｛ｖ?－?Ｔｊ－，０｝，??其形狀如圖２．１（ａ）所示。??／（＾）｜??ｍ；?ａｖ??０?ｖ?ｒｊ?〇?ｖ?ｒｊ??（ａ）?（ｂ）??圖２．１：釋放時(shí)間的兩類資源消費(fèi)曲線??以向量７Ｔ?＝?｛?Ｊ丨１］；?？?？?？，ＪＷ｝記錄工件集Ｊ的一個(gè)工件序列，其中Ｊｂ］＝厶表示人是??安排在序列的第ｊ個(gè)位置，向量ｒ?＝伏⑴，．．．，７＾｝記工件序列７Ｔ對(duì)應(yīng)的釋放時(shí)間。假定??ＩＩ為所有可行工件序列的集合，丑為釋放時(shí)間７■的可行集合。定義總成本Ｚ（７Ｔ，ｒ：）為??ｎ?ｎ?ｎ??Ｚ（ｔｔ；?＝?／（％］）?＋?６?＋?Ｊ２ｐｌ＾?＋?＾?＋?Ｐｈｉ）－??ｉ＝ｉ?ｉ＝ｊ?ｊ＝ｉ??顯然，項(xiàng)Ｕ＝１／（ｒｂ．］）是釋放成本，ｍａｘｗＷｒｙｊ?＋?Ｅｂ外ｊ｝是時(shí)間表長(zhǎng)，＾４（７＾＋削）??是總完工時(shí)間。我們的目標(biāo)是找一個(gè)最優(yōu)工件序列ｔｔ＊和它對(duì)應(yīng)的釋放時(shí)間序列使??得??Ｚ（７ｒ＊，ｒ＊）?＝?ｍｉｎ?Ｚ（７ｒ，ｒ）．??７ｒｅＵ

理：??引理２．１．最優(yōu)解中工件之間不含空閑時(shí)間。??證明．如圖２．２所示，當(dāng)工件之間含有空隙的話，我們可以證明消除該空隙可以減小調(diào)度??成本。對(duì)于給定的一個(gè)可行解（７Ｔ，７〇，其成本為Ｚ（７Ｔ，ｒ）。假定存在某個(gè)正整數(shù)Ａ：（０?＜?／ｃ?＜?ｎ）??使得?ｒ［＊：ｊ?＋ｐ間?＜?ｒ［ｆｃ＋１］并記該空隙長(zhǎng)為?Ａ?＝?ｒ［；；＋１］?—?（ｒ［ｆｃｊ?＋ｐ［＊］）。??下面我們可以通過(guò)改變工件序列ｒ中部分工件的實(shí)際釋放時(shí)間，消除工件和??七＋１丨之間的空閑，構(gòu)造一個(gè)新的可行解㈨，其成本為Ｚ（７Ｔ，Ｔ＇），使得Ｚ（７Ｔ，＜?Ｚ（７Ｔ，。??情形Ｉ：?ｒ＜ｒｗ＋糊。??將序列ｔｔ中空閑后ｎ?－?個(gè)工件向前移動(dòng)Ａ個(gè)單位，也就是令實(shí)際釋放時(shí)間??Ｔ?一（『［１］?’?？?．?？?’『［ｎ］）?＿?（『［Ｉ］?’?？?？?？，『［Ａ；］?’?—么，．？?？，ｒ問(wèn)一?Ａ），??１９??


本文編號(hào)：3630466