A best possible on-line algorithm for scheduling on uniform parallel-batch machines

作者：Li, Wenhua^*; Chai, Xing; Song, Yali

来源：Theoretical Computer Science, 2018, 740: 68-75.

DOI：10.1016/j.tcs.2018.05.014

• On-line algorithm
• Uniform machines
• Parallel-batch
• Makespan
• Competitive ratio

An on-line scheduling problem on m uniform parallel-batch machines to minimize the makespan is considered in this paper. Each machine can process infinite jobs as a batch at a time. Jobs arrive over time and have equal lengths denoted by 1. Compared to parallel machines, uniform machines are more difficult to deal with because they have different processing speeds. There are two types of machines in our model. The lower bound on the competitive ratio is characterized by some complicated algebraic equations. And a best possible on-line algorithm matching the lower bound is constructed and proved in this paper.

• 出版日期2018-9-5
• 单位郑州大学