本文選題：在線排序 + 相容性��； 參考：《中國礦業(yè)大學(xué)》2017年碩士論文

【摘要】：所謂排序,即在一定的資源限制下更好地安排和完成一些任務(wù),使得期望的效益或目標(biāo)達到最優(yōu)值或理想值。排序論在工業(yè)制造領(lǐng)域,計算機科學(xué),物流運輸管理等領(lǐng)域都有廣泛地應(yīng)用,具有重要的理論研究價值和廣泛的應(yīng)用前景。本論文主要研究的是工件具有相容性的多臺平行分批處理機的在線排序問題。在線排序是指每個工件都有一個到達時間,決策者在工件到達之后才知曉其信息。對到達的工件,排序者可以立即安排加工,也可推遲安排加工。平行分批排序是指工件在加工過程中被分成若干批,每個批中允許同時放置多個工件,但工件總數(shù)不得超過批容量。批容量通常分為有限和無限兩種情形。同一批中的工件有相同的開工時間和完工時間。批的加工時間定義為該批中加工時間最大的工件的加工時間。工件具有相容性約束一般分為兩種類型:(1)工件具有區(qū)間相容性;(2)工件屬于不同的工件組。工件具有區(qū)間相容性是指,每一個工件都有一個可以用區(qū)間表示的信息,兩個工件相容當(dāng)且僅當(dāng)兩工件的區(qū)間相交,此時,二者可以放在同一個批中加工。工件屬于不同工件組是指任意一個工件都屬于某個確定的工件組,只有同一個工件組中的工件才能夠放在同一個批中加工。本文研究的排序問題的目標(biāo)函數(shù)是最小化最大完工時間。本文的主要成果如下:(1)對排序問題pm=|on-line,rj,G=INT,p-batch,b=∞|Cmax,本文證明了任意一個在線算法的競爭比都不小于2,并設(shè)計出競爭比為2+(m-1)/(m+1)的在線算法,且該在線算法是單機情形下的一個最優(yōu)在線算法;對工件加工時間相同的特殊情形,設(shè)計出了一個競爭比為2的最優(yōu)在線算法。(2)對排序問題pm|on-line,rj,family,p-batch,b=∞|Cmax,本文證明了任意一個在線算法的競爭比都不小于2,并設(shè)計出了一個競爭比為7/3-1/(3m)的在線算法,且證明這個界是可達的;對工件加工時間相同的特殊情形,設(shè)計出了一個競爭比為2的最優(yōu)在線算法。
[Abstract]:The so-called sorting is to arrange and complete some tasks better under certain resource constraints, so that the desired benefit or goal can reach the optimal value or ideal value. Sequencing theory has been widely used in the field of industrial manufacturing, computer science, logistics and transportation management, etc. It has important theoretical research value and wide application prospect. In this paper, the problem of online scheduling of parallel batch processors with compatible workpiece is studied. On-line sorting means that each artifact has a time of arrival, and the decision maker does not know the information until the arrival of the artifact. To arrive the workpiece, the sorter may arrange the processing immediately, may also delay the arrangement processing. Parallel batch ranking refers to the number of jobs being divided into lots in the process of processing, in which multiple jobs are allowed to be placed simultaneously, but the total number of jobs must not exceed the batch capacity. Batch capacity is usually divided into two cases: finite and infinite. The same batch of workpieces have the same start-up time and completion time. The processing time of the batch is defined as the processing time of the workpiece with the longest processing time in the batch. Jobs with compatibility constraints are generally divided into two types: 1) workpieces have interval compatibility and / or 2) workpieces belong to different workpiece groups. An interval-compatible workpiece means that each workpiece has an information that can be represented by an interval, and that two jobs are compatible if and only if the intersections of two jobs intersect, in which case they can be processed in the same batch. Jobs belonging to different job groups refer to that any job belongs to a certain workpiece group. Only jobs in the same workpiece group can be processed in the same batch. The objective function of the sorting problem studied in this paper is to minimize the maximum completion time. The main results of this paper are as follows: (1) in this paper, we prove that the competition ratio of any online algorithm is not less than 2, and design an online algorithm with a competition ratio of 2 m ~ (-1) / m ~ (1). The on-line algorithm is an optimal on-line algorithm in the case of a single machine, and for the special case where the workpiece processing time is the same, In this paper, we design an optimal online algorithm with a competition ratio of 2. We design an online algorithm for the ordering problem: pm on-line family p-batchnb = 鈭，

本文編號：1807373