Back to Search
Start Over
THE NP-HARDNESS OF MINIMIZING THE TOTAL LATE WORK ON AN UNBOUNDED BATCH MACHINE.
- Source :
- Asia-Pacific Journal of Operational Research; Jun2009, Vol. 26 Issue 3, p351-363, 13p
- Publication Year :
- 2009
-
Abstract
- We consider the problem of minimizing the total late work (Σ<subscript>j=1</subscript><superscript>n</superscript> V<subscript>j</subscript>) on an unbounded batch processing machine, where V<subscript>j</subscript> = min{T<subscript>j</subscript>, p<subscript>j</subscript>} and T<subscript>j</subscript> = max{C<subscript>j</subscript> - d<subscript>j</subscript>, O}. The batch processing machine can process up to B (B ≥ n) jobs simultaneously. The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time, respectively. For a batch of jobs, the processing time of the batch is equal to the largest processing time among the jobs in this batch. In this paper, we prove that the problem 1∣B ≥ n∣ Σ<subscript>j=1</subscript><superscript>n</superscript>V<subscript>j</subscript> is NP-hard. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02175959
- Volume :
- 26
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- Asia-Pacific Journal of Operational Research
- Publication Type :
- Academic Journal
- Accession number :
- 44196535
- Full Text :
- https://doi.org/10.1142/S0217595909002249