【摘要】：研究以最小化最大完工時(shí)間為目標(biāo)、批容量有界的并行分批在線排序問題。相應(yīng)排序模型中有n個(gè)相互獨(dú)立的工件要在一臺(tái)批處理機(jī)上加工,每個(gè)工件Jj(1≤j≤n)具有一到達(dá)時(shí)間rj和加工時(shí)間p_j,工件的加工時(shí)間非增,即對(duì)于任意2個(gè)工件Ji和Jj,如果r_i≤r_j,則p_i≥p_j。批處理機(jī)每次可同時(shí)加工至多B B(n)個(gè)工件。同一批中的工件同時(shí)開工,同時(shí)完工,任一工件的信息(包括它的到達(dá)時(shí)間、加工時(shí)間)需等到它到達(dá)時(shí)系統(tǒng)才能獲取,研究任務(wù)是設(shè)計(jì)一個(gè)在線算法對(duì)工件進(jìn)行合理地分批和排序以使得最大完工時(shí)間達(dá)到最小。首先證明該在線排序問題不存在競(jìng)爭(zhēng)比小于1+α(其中α~2+α=1)的在線算法,然后設(shè)計(jì)一在線算法,證明它的競(jìng)爭(zhēng)比等于1+α,從而證明它的最優(yōu)性。
[Abstract]:In this paper, the parallel batch online scheduling problem with bounded batch capacity is studied, which aims at minimizing the maximum completion time. In the corresponding sorting model, there are n independent workpieces to be processed on a batch processor, each workpiece Jj (1 鈮，

本文編號(hào)：2507676