本文選題：在線調(diào)度 + 半在線調(diào)度　； 參考：《上海交通大學(xué)》2014年博士論文

【摘要】：在線或半在線調(diào)度作為一種信息匱缺情況下的優(yōu)化決策問題,廣泛存在于生產(chǎn)制造、通信網(wǎng)絡(luò)、電力系統(tǒng)、交通運輸及公共服務(wù)系統(tǒng)等領(lǐng)域。由于缺乏完整信息,一般不能建立基于問題完整描述的優(yōu)化算法,此外,在線調(diào)度在很多情況下還有實時性要求,這使得大部分在線調(diào)度都采用一些計算要求簡單的分派規(guī)則,由于這些規(guī)則多為啟發(fā)式的,即使應(yīng)用到相同問題的不同實例也可能出現(xiàn)性能差異甚遠(yuǎn)的情況。因此,為了對規(guī)則的選擇和應(yīng)用提供理論支持,還需分析研究相應(yīng)調(diào)度算法的競爭性能。 在競爭分析的歷史研究中,采用的很多方法都具有很強(qiáng)的問題依賴性,證明分析都依賴于一些輔助調(diào)度的巧妙構(gòu)造,過程通常也顯得相當(dāng)繁瑣,精妙有余而規(guī)律性不強(qiáng)。本文首先嘗試進(jìn)行競爭比分析方法的研究,提出了一種基于實例空間壓縮的較為一般的分析方法,然后將其應(yīng)用到多個在線及加工時間有界的半在線調(diào)度問題的算法設(shè)計與競爭分析上,歸納起來,本論文的研究內(nèi)容主要包括以下四個方面： ·提出了一種新穎的基于實例空間壓縮的競爭比分析方法,闡述了該方法的基本思想及常用的空間壓縮方法,并將該方法應(yīng)用于最小化總完工時間及總加權(quán)完工時間的單機(jī)調(diào)度,針對現(xiàn)有的兩個最優(yōu)在線算法,分別給出了替代的競爭比證明。 ·研究了最小化總加權(quán)完工時間的同速并行機(jī)在線調(diào)度通過擴(kuò)展相應(yīng)單機(jī)及非加權(quán)情況下的在線算法,提出了基于組合延時的CD-SWPT算法,并采用基于實例空間壓縮的分析方法,證明了該算法的競爭比位于[2,2.5-1/2m]之間。 ·研究了加工時間有界的最小化總完工時間及總加權(quán)完工時間的單機(jī)半在線調(diào)度問題,針對提出了αD-SPT算法,并應(yīng)用基于實例空間壓縮的方法證明其競爭比為針對γ|∑ωjCj,提出了αD-SWPT算法,并應(yīng)用基于實例空間壓縮的方法證明了其競爭比為同時證明了該競爭比也是針對該問題的任何半在線算法所能取得的最好結(jié)果。 ·針對加工時間有界的最小化總加權(quán)流通時間的單機(jī)半在線調(diào)度及同速并行機(jī)半在線調(diào)度采用基于實例空間壓縮的方法分別分析了SWPT規(guī)則的競爭性能,證明了SWPT針對單機(jī)情形為最優(yōu)的半在線算法,相應(yīng)的競爭比為γ+1,針對并行機(jī)情形其競爭比位于[γ+1,γ+1.5-1/2m]之間。
[Abstract]:As an optimal decision making problem in the absence of information, online or semi-online scheduling is widely used in manufacturing, communication networks, power systems, transportation and public service systems. Because of the lack of complete information, the optimization algorithm based on the complete description of the problem can not be established generally. In addition, there are real-time requirements in many cases for online scheduling, which makes most online scheduling adopt some simple dispatch rules that require simple computation. As most of these rules are heuristic, even if they are applied to different instances of the same problem, the performance may vary greatly. Therefore, in order to provide theoretical support for the selection and application of rules, it is necessary to analyze and study the competitive performance of the corresponding scheduling algorithms. In the historical study of competition analysis, many of the methods used have strong problem dependence. It is proved that the analysis depends on the ingenious construction of some auxiliary scheduling, and the process is usually very complicated, subtle and irregular. In this paper, we first try to study the competitive ratio analysis method, and propose a more general analysis method based on case space compression. Then it is applied to the algorithm design and competition analysis of multiple online and semi-online scheduling problems with bounded processing time. In summary, the research contents of this paper mainly include the following four aspects: A novel competitive ratio analysis method based on case space compression is proposed. The method is applied to single machine scheduling which minimizes the total completion time and the total weighted completion time. For the existing two optimal online algorithms, the alternative competitive ratio proof is given respectively. In this paper, the on-line scheduling of parallel machines at the same speed, which minimizes the total weighted completion time, is studied. By extending the corresponding on-line algorithms in the case of single machine and non-weighted case, the CD-SWPT algorithm based on combinatorial delay is proposed, and the analysis method based on case space compression is adopted. It is proved that the competitive ratio of the algorithm is between [2] 2. 5-1 / 2 m. In this paper, the semi-on-line scheduling problem of single machine with bounded processing time to minimize the total completion time and the total weighted completion time is studied, and a 偽 D-SPT algorithm is proposed to solve the problem. The case based space compression method is used to prove that the competition ratio is 緯 鈭，

本文編號：1931866