工件加工时间非增的并行分批排序问题的最优在线算法

发布时间：2019-06-29 08:01

【摘要】：研究以最小化最大完工时间为目标、批容量有界的并行分批在线排序问题。相应排序模型中有n个相互独立的工件要在一台批处理机上加工,每个工件Jj(1≤j≤n)具有一到达时间rj和加工时间p_j,工件的加工时间非增,即对于任意2个工件Ji和Jj,如果r_i≤r_j,则p_i≥p_j。批处理机每次可同时加工至多B B(n)个工件。同一批中的工件同时开工,同时完工,任一工件的信息(包括它的到达时间、加工时间)需等到它到达时系统才能获取,研究任务是设计一个在线算法对工件进行合理地分批和排序以使得最大完工时间达到最小。首先证明该在线排序问题不存在竞争比小于1+α(其中α~2+α=1)的在线算法,然后设计一在线算法,证明它的竞争比等于1+α,从而证明它的最优性。
[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