Paper Info
Title
Single-machine makespan minimization scheduling with nonlinear shortening processing times
Abstract
In this paper, we consider the single-machine makespan minimization scheduling problem with nonlinear shortening processing times. By the nonlinear shortening processing times, we mean that the processing times of jobs are non-increasing nonlinear functions of their starting times. The computational complexity of the general problem remains an open problem, but we show that even with the introduction of nonlinear shortening processing times to job processing times, some special cases remain polynomially solvable. We also show that an optimal schedule of the general makespan minimization problem is V-shaped with respect to job normal processing times. A heuristic algorithm which utilize the V-shaped property is proposed, and computational experiments show that it is effective and efficient in obtaining near-optimal solutions.
Year
DOI
Venue
2012
10.1016/j.cor.2011.05.001
Computers & OR
Keywords
DocType
Volume
open problem,Single-machine makespan minimization scheduling,nonlinear function,nonlinear shortening processing time,processing time,Nonlinear shortening processing times,Single-machine,general problem,Scheduling,Makespan,general makespan minimization problem,computational complexity,job processing time,V-shaped property,job normal processing time
Journal
39
Issue
ISSN
Citations 
3
Computers and Operations Research
0
PageRank 
References 
Authors
0.34
10
2
Name
Order
Citations
PageRank
Mingzheng Wang125115.78
Jibo Wang274541.50