Batch scheduling of step deteriorating jobs |
| |
Authors: | M S Barketau T C E Cheng C T Ng Vladimir Kotov Mikhail Y Kovalyov |
| |
Affiliation: | (1) Belarusian State University, Nezavisimosti 4, 220030 Minsk, Belarus;(2) Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong;(3) United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6, 220012 Minsk, Belarus |
| |
Abstract: | In this paper we consider the problem of scheduling n jobs on a single machine, where the jobs are processed in batches and the processing time of each job is a step function
depending on its waiting time, which is the time between the start of the processing of the batch to which the job belongs
and the start of the processing of the job. For job i, if its waiting time is less than a given threshold value D, then it requires a basic processing time a
i
; otherwise, it requires an extended processing time a
i
+b
i
. The objective is to minimize the completion time of the last job. We first show that the problem is NP-hard in the strong
sense even if all b
i
are equal, it is NP-hard even if b
i
=a
i
for all i, and it is non-approximable in polynomial time with a constant performance guarantee Δ<3/2, unless
. We then present O(nlog n) and O(n
3F−1log n/F
F
) algorithms for the case where all a
i
are equal and for the case where there are F, F≥2, distinct values of a
i
, respectively. We further propose an O(n
2log n) approximation algorithm with a performance guarantee
for the general problem, where m
* is the number of batches in an optimal schedule. All the above results apply or can be easily modified for the corresponding
open-end bin packing problem. |
| |
Keywords: | Batching Scheduling Deterioration Open-end bin packing |
本文献已被 SpringerLink 等数据库收录! |
|