Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/11743
Title: Scheduling Jobs with Piecewise Linear Decreasing Processing Times
Authors: Cheng, TCE 
Ding, Q
Kovalyov, MY
Bachman, A
Janiak, A
Keywords: Computational complexity
Machine scheduling
Start time dependent processing times
Issue Date: 2003
Publisher: John Wiley & Sons
Source: Naval research logistics, 2003, v. 50, no. 6, p. 531-554 How to cite?
Journal: Naval research logistics 
Abstract: We study the problems of scheduling a set of nonpreemptive jobs on a single or multiple machines without idle times where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objectives are the minimization of makespan and minimization of total job completion time. The single machine problems are proved to be NP-hard, and some properties of their optimal solutions are established. A pseudopolynomial time algorithm is constructed for makespan minimization. Several heuristics are derived for both total completion time and makespan minimization. Computational experiments are conducted to evaluate their efficiency. NP-hardness proofs and polynomial time algorithms are presented for some special cases of the parallel machine problems.
URI: http://hdl.handle.net/10397/11743
ISSN: 0894-069X
EISSN: 1520-6750
DOI: 10.1002/nav.10073
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

45
Last Week
0
Last month
0
Citations as of May 11, 2018

WEB OF SCIENCETM
Citations

45
Last Week
0
Last month
0
Citations as of May 19, 2018

Page view(s)

80
Last Week
2
Last month
Citations as of May 21, 2018

Google ScholarTM

Check

Altmetric


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