The unbounded parallel-batch scheduling with rejection
In this paper, we consider the unbounded parallel-batch scheduling with rejection. A job is either rejected, in which case a certain penalty has to be paid, or accepted and processed in batches on a machine. The processing time of a batch is defined as the longest processing time of the jobs contained in it. Four problems are considered: (1) to minimize the sum of the total completion time of the accepted jobs and the total rejection penalty of the rejected jobs; (2) to minimize the total completion time of the accepted jobs subject to an upper bound on the total rejection penalty of the rejected jobs; (3) to minimize the total rejection penalty of the rejected jobs subject to an upper bound on the total completion time of the accepted jobs; (4) to find the set of all the Pareto optimal schedules. We provide a polynomial-time algorithm for the first problem. Furthermore, we show that all the other three problems are binary NP-hard and present a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme for them.
Year of publication: |
2012
|
---|---|
Authors: | Zhang, L Q ; Lu, L F ; Ng, C T |
Published in: |
Journal of the Operational Research Society. - Palgrave Macmillan, ISSN 0160-5682. - Vol. 63.2012, 3, p. 293-298
|
Publisher: |
Palgrave Macmillan |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
The unbounded parallel-batch scheduling with rejection
Zhang, L Q, (2012)
-
Multi-period empty container repositioning with stochastic demand and lost sales
Zhang, B, (2014)
-
The loader problem: formulation, complexity and algorithms
Tang, G, (2010)
- More ...