论文标题
基于多个列表调度模型的最小加载机上的2竞争性最大作业
A 2-Competitive Largest Job on Least Loaded Machine Online Algorithm based on Multi Lists Scheduling Model
论文作者
论文摘要
在相同的机器中使用MakePAN最小化的在线调度已经是文献中研究的研究问题。在在线计划中，调度程序将一一接收一份作业列表，并在下一个作业到达之前，将每个传入的作业不可撤销地分配给其中一台机器。在本文中，我们研究了在线调度问题的一种变体，在该问题中，从k个不同的来源开始要求工作。在来自多个来源的工作同时到达后，这是一项非平凡的研究挑战，旨在确保在不同的来源计划方面的公平性，同时优化时间表的整体制造商。我们开发了一种新颖的多列表调度模型（MLS），并提出了一种基于MLS模型的最大载荷机器（LJLLM）的2竞争性确定性在线算法，即解决上述研究挑战。
Online scheduling in identical machines with makespan minimization has been a well studied research problem in the literature. In online scheduling, the scheduler receives a list of jobs one by one and assigns each incoming job on the fly irrevocably to one of the machines before the arrival of the next job. In this paper, we study a variant of the online scheduling problem, where jobs are requested on the fly from k distinct sources. On simultaneous arrival of jobs from multiple sources, it is a non-trivial research challenge to ensure fairness in scheduling with respect to distinct sources, while optimizing the overall makespan of the schedule. We develop a novel Multi Lists Scheduling Model(MLS) and propose a 2-competitive deterministic online algorithm namely Largest Job on Least Loaded Machine(LJLLM) based on the MLS model to address the above mentioned research challenge.
