Copy
Toshihide IBARAKI, Hiroshi KISE, Hisashi MINE, "Parallel-Machine Scheduling Problem with Unit Processing Time When Jobs Have Ready and Due Times" in IEICE TRANSACTIONS on transactions,
vol. E59-E, no. 7, pp. 1-6, July 1976, doi: .
Abstract: Let J{1, 2, , n} be a set of jobs. Each job j can be processed on one of the m identical machines in one unit time, and has ready and due times. It is shown that the problem of finding an optimal schedule minimizing the sum of costs associated with jobs j, which are monotone functions of completion time of j, can be reduced to the assignment problem with 0(n) vertices; hence it can be solved in 0(n3) steps. As important special cases, this cost includes the weighted number of late jobs, the weighted tardiness, and the weighted flow-time. In addition, it is shown that the problem has an 0(n log n) algorithm if the objective is to minimize the (unweighted) number of late jobs. This problem is critical for having an efficient algorithm in the sense that generalizing it in various directions easily results in NP-complete problems. As an example, it is shown that it becomes NP-complete if precedence constraints are imposed.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e59-e_7_1/_p
Copy
@ARTICLE{e59-e_7_1,
author={Toshihide IBARAKI, Hiroshi KISE, Hisashi MINE, },
journal={IEICE TRANSACTIONS on transactions},
title={Parallel-Machine Scheduling Problem with Unit Processing Time When Jobs Have Ready and Due Times},
year={1976},
volume={E59-E},
number={7},
pages={1-6},
abstract={Let J{1, 2, , n} be a set of jobs. Each job j can be processed on one of the m identical machines in one unit time, and has ready and due times. It is shown that the problem of finding an optimal schedule minimizing the sum of costs associated with jobs j, which are monotone functions of completion time of j, can be reduced to the assignment problem with 0(n) vertices; hence it can be solved in 0(n3) steps. As important special cases, this cost includes the weighted number of late jobs, the weighted tardiness, and the weighted flow-time. In addition, it is shown that the problem has an 0(n log n) algorithm if the objective is to minimize the (unweighted) number of late jobs. This problem is critical for having an efficient algorithm in the sense that generalizing it in various directions easily results in NP-complete problems. As an example, it is shown that it becomes NP-complete if precedence constraints are imposed.},
keywords={},
doi={},
ISSN={},
month={July},}
Copy
TY - JOUR
TI - Parallel-Machine Scheduling Problem with Unit Processing Time When Jobs Have Ready and Due Times
T2 - IEICE TRANSACTIONS on transactions
SP - 1
EP - 6
AU - Toshihide IBARAKI
AU - Hiroshi KISE
AU - Hisashi MINE
PY - 1976
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E59-E
IS - 7
JA - IEICE TRANSACTIONS on transactions
Y1 - July 1976
AB - Let J{1, 2, , n} be a set of jobs. Each job j can be processed on one of the m identical machines in one unit time, and has ready and due times. It is shown that the problem of finding an optimal schedule minimizing the sum of costs associated with jobs j, which are monotone functions of completion time of j, can be reduced to the assignment problem with 0(n) vertices; hence it can be solved in 0(n3) steps. As important special cases, this cost includes the weighted number of late jobs, the weighted tardiness, and the weighted flow-time. In addition, it is shown that the problem has an 0(n log n) algorithm if the objective is to minimize the (unweighted) number of late jobs. This problem is critical for having an efficient algorithm in the sense that generalizing it in various directions easily results in NP-complete problems. As an example, it is shown that it becomes NP-complete if precedence constraints are imposed.
ER -
English
