Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs

被引：46

作者：

Hiraishi, K

Levner, E

Vlach, M

机构：

[1] Japan Adv Inst Sci & Technol, Sch Informat Sci, Tatsunokuchi, Ishikawa 9231292, Japan

[2] Holon Inst Technol, IL-58102 Holon, Israel

来源：

COMPUTERS & OPERATIONS RESEARCH | 2002年 / 29卷 / 07期

基金：

日本学术振兴会;

关键词：

scheduling; parallel machines; irregular objective; just-in-time; set-up times; polynomial algorithm;

D O I：

10.1016/S0305-0548(00)00086-1

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We study the problem of nonpreemptively scheduling n jobs on m identical machines in parallel to maximize the weighted number of jobs that are completed exactly at their due dates. We show that this problem is solvable in polynomial time even if positive set-up times are allowed. Moreover, we show that if due date tolerances are permitted, then already the single-machine case is NP-hard even if all set-up times are zero and all weights are the same.

引用

页码：841 / 848

页数：8