期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 244, 期 1, 页码 86-99出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2015.01.003
关键词
Single machine scheduling; Two competing agents; Equal processing times; Complexity
We study various two-agent scheduling problems on a single machine with equal job processing times. The equal processing time assumption enables us to design new polynomial-time or faster-than-known optimization algorithms for many problems. We prove, however, that there exists a subset of problems for which the computational complexity remains NP-hard. The set of hard problems includes different variations where the objective functions of the two agents are either minimizing the weighted sum of completion times or the weighted number of tardy jobs. For these problems, we present pseudo-polynomial time algorithms. Crown Copyright (C) 2015 Published by Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据