期刊
INFORMATION PROCESSING LETTERS
卷 90, 期 6, 页码 273-278出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ipl.2004.03.004
关键词
approximation algorithms; flow shop scheduling; worst-case analysis
We study the problem of scheduling n jobs in a two-machine flow shop where the second machine is not available for processing during a given time interval. A resumable scenario is assumed, i.e., if a job cannot be finished before the down period it is continued after the machine becomes available again. The objective is to minimize the makespan. The best fast approximation algorithm for this problem guarantees a relative worst-case error bound of 4/3. We present an improved algorithm with a relative worst-case error bound of 5/4. (C) 2004 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据