Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/475
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 | Size | Format | |
---|---|---|---|---|
V4_06[1].11.21.pdf | Pre-published version | 159.81 kB | Adobe PDF | View/Open |
Page views
78
Last Week
1
1
Last month
Citations as of Mar 24, 2024
Downloads
143
Citations as of Mar 24, 2024
SCOPUSTM
Citations
18
Last Week
0
0
Last month
1
1
Citations as of Mar 28, 2024
WEB OF SCIENCETM
Citations
15
Last Week
0
0
Last month
0
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.