【摘要】：研究以最小化最大完工時間為目標(biāo)、批容量有界的并行分批在線排序問題。相應(yīng)排序模型中有n個相互獨(dú)立的工件要在一臺批處理機(jī)上加工,每個工件Jj(1≤j≤n)具有一到達(dá)時間rj和加工時間p_j,工件的加工時間非增,即對于任意2個工件Ji和Jj,如果r_i≤r_j,則p_i≥p_j。批處理機(jī)每次可同時加工至多B B(n)個工件。同一批中的工件同時開工,同時完工,任一工件的信息(包括它的到達(dá)時間、加工時間)需等到它到達(dá)時系統(tǒng)才能獲取,研究任務(wù)是設(shè)計(jì)一個在線算法對工件進(jìn)行合理地分批和排序以使得最大完工時間達(dá)到最小。首先證明該在線排序問題不存在競爭比小于1+α(其中α~2+α=1)的在線算法,然后設(shè)計(jì)一在線算法,證明它的競爭比等于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 鈮，

本文編號：2507676