Single-Machine Scheduling Problems with Two Agents Competing for Makespan
This paper considers the single-machine scheduling problems in which two distinct agents are concerned. Each agent has a set of jobs with different release times, and both of them expect to complete their respective jobs as early as possible. We take the makespan of each agent as its own criterion and take the linear combination of the two makespans as our objective function. In this paper, both off-line and online models are considered. When preemption is allowed, we present an exact algorithm for the offline model and an optimal algorithm for the on-line model. When preemption is not allowed we point out that the problem is NP-hard for the off-line model and give a (2+ l/θ)-competitive algorithm for the on-line model. We also prove that a lower bound of the competitive ratio for the later model is 1 + θ/(1 + θ), where θ is a given factor not less than 1.
Guosheng Ding Shijie Sun
Department of Mathematics, Shanghai University, Shanghai, China School of Science, Nantong Universit Department of Mathematics, Shanghai University, Shanghai, China
国际会议
无锡
英文
244-255
2010-09-17（万方平台首次上网日期，不代表论文的发表时间）