Scheduling Jobs with Release and Delivery Times Subject to Nested Eligibility Constraints

被引：0
|
作者：
Yu-Zhong Zhang
Shu-Guang Li
机构：
[1] Qufu Normal University,Institute of Operations Research
[2] Key Laboratory of Intelligent Information Processing in Universities of Shandong (Shandong Institute of Business and Technology),College of Computer Science and Technology
[3] Shandong Institute of Business and Technology,undefined
来源：
Journal of the Operations Research Society of China | 2021年 / 9卷
关键词：
Scheduling; Nested eligibility constraints; Release time; Delivery time; Polynomial time approximation scheme; 90B35; 68M20;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The problem of scheduling jobs with release and delivery time subject to machine eligibility constraints is considered. The eligible sets of the jobs are nested, and preemptions are not allowed. The goal is to minimize the maximum delivery completion time, i.e., the time by which all jobs are delivered. For the special case of equal release time, a 2-approximation algorithm is presented whose running time depends linearly on the number of jobs. For the general case of unequal release time, a polynomial time approximation scheme is derived.
引用
收藏
页码：63 / 77
页数：14
相关论文
共 50 条
12345