Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/36295
Title: Single-machine batch scheduling of linear deteriorating jobs
Authors: Ji, M
Yang, QY
Yao, DL
Cheng, TCE 
Keywords: Scheduling
Deteriorating jobs
Batch
NP-hardness
FPTAS
Non-approximability
Issue Date: 2015
Publisher: Elsevier
Source: Theoretical computer science, 2015, v. 580, p. 36-49 How to cite?
Journal: Theoretical computer science 
Abstract: We consider the problem of scheduling jobs in batches on a single machine where the processing time of each job is a simple increasing linear function of its waiting time, i.e., the time between the starting time of processing the batch to which the job belongs and the starting time of processing of the job. The objective is to minimize the sum of the total job flow time and the batching cost. We first show that the case with a given number of batches is strongly NP-hard and we present a fully polynomial-time approximation scheme (FPTAS) for this case. We then show that the case with an arbitrary number of batches is also strongly NP-hard and there is no polynomial-time approximation algorithm with a constant upper bound for this case unless P = NP.
URI: http://hdl.handle.net/10397/36295
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2015.02.025
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

WEB OF SCIENCETM
Citations

1
Last Week
0
Last month
Citations as of Feb 19, 2017

Page view(s)

9
Last Week
0
Last month
Checked on Feb 19, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.