Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/475
PIRA download icon_1.1View/Download Full Text
Title: An FPTAS for scheduling with piecewise linear decreasing processing times to minimize makespan
Authors: Ji, M
Cheng, TCE 
Issue Date: 30-Apr-2007
Source: An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan. Information processing letters, Apr. 2007, v. 102, no. 2-3, p. 41-47
Abstract: We study the problems of scheduling a set of nonpreemptive jobs on a single machine and identical parallel machines, where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objective is to minimize makespan. We first give a fully polynomial-time approximation scheme (FPTAS) for the case with a single machine. We then generalize the result to the case with m identical machines.
Keywords: Machine scheduling
Start time-dependent processing times
Makespan
Approximation algorithms
Publisher: Elsevier
Journal: Information processing letters 
ISSN: 0020-0190
DOI: 10.1016/j.ipl.2006.11.014
Rights: Information Processing Letters © 2006 Elsevier. The journal web site is located at http://www.sciencedirect.com.
Appears in Collections:Journal/Magazine Article

Files in This Item:
File Description SizeFormat 
V4_06[1].11.21.pdfPre-published version159.81 kBAdobe PDFView/Open
Open Access Information
Status open access
File Version Final Accepted Manuscript
Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page views

78
Last Week
1
Last month
Citations as of Mar 24, 2024

Downloads

143
Citations as of Mar 24, 2024

SCOPUSTM   
Citations

18
Last Week
0
Last month
1
Citations as of Mar 28, 2024

WEB OF SCIENCETM
Citations

15
Last Week
0
Last month
0
Citations as of Mar 28, 2024

Google ScholarTM

Check

Altmetric


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