Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/29095
Title: Single machine scheduling with a restricted rate-modifying activity
Authors: He, Y
Ji, M
Cheng, TCE 
Keywords: Approximation algorithms
Computational complexity
Rate-modifying activity
Scheduling
Issue Date: 2005
Publisher: John Wiley & Sons
Source: Naval research logistics, 2005, v. 52, no. 4, p. 361-369 How to cite?
Journal: Naval research logistics 
Abstract: In this paper we consider the problem of scheduling a set of jobs on a single machine on which a rate-modifying activity may be performed. The rate-modifying activity is an activity that changes the production rate of the machine. So the processing time of a job is a variable, which depends on whether it is scheduled before or after the rate-modifying activity. We assume that the rate-modifying activity can take place only at certain predetermined time points, which is a constrained case of a similar problem discussed in the literature. The decisions under consideration are whether and when to schedule the rate-modifying activity, and how to sequence the jobs in order to minimize some objectives. We study the problems of minimizing makespan and total completion time. We first analyze the computational complexity of both problems for most of the possible versions. The analysis shows that the problems are NP-hard even for some special cases. Furthermore, for the NP-hard cases of the makespan problem, we present a pseudo-polynomial time optimal algorithm and a fully polynomial time approximation scheme. For the total completion time problem, we provide a pseudo-polynomial time optimal algorithm for the case with agreeable modifying rates.
URI: http://hdl.handle.net/10397/29095
ISSN: 0894-069X
EISSN: 1520-6750
DOI: 10.1002/nav.20083
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

25
Last Week
0
Last month
0
Citations as of Aug 21, 2017

WEB OF SCIENCETM
Citations

20
Last Week
0
Last month
0
Citations as of Aug 20, 2017

Page view(s)

38
Last Week
0
Last month
Checked on Aug 20, 2017

Google ScholarTM

Check

Altmetric



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