Single-machine scheduling with nonlinear deterioration |
| |
Authors: | Ji-Bo Wang Ming-Zheng Wang |
| |
Institution: | 1. School of Science, Shenyang Aerospace University, Shenyang, 110136, China 2. School of Management Science and Engineering, Dalian University of Technology, Dalian, 116024, China
|
| |
Abstract: | In this paper, we consider the single-machine scheduling problems with nonlinear deterioration. By the nonlinear deterioration
effect, we mean that the processing times of jobs are nonlinear functions of their starting times. We show that even with
the introduction of nonlinear deterioration to job processing times, single machine makespan minimization problem remains
polynomially solvable. We also show that an optimal schedule of the total completion time minimization problem is V-shaped
with respect to job normal processing times. A heuristic algorithm utilizing the V-shaped property is proposed, and computational
experiments show that it performs effectively and efficiently in obtaining near-optimal solutions. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|