IJPAM: Volume 13, No. 4 (2004)

SINGLE-MACHINE SCHEDULING TO MINIMIZE
MAKESPAN UNDER LINEAR DETERIORATION

Ji-Bo Wang$^1$, Ming-Zheng Wang$^2$, Zun-Quan Xia$^3$
$^{1,2,3}$Department of Applied Mathematics
Dalian University of Technology
Dalian 116024, P.R. CHINA
$^1$e-mail: wjb7575@sina.com


Abstract.This paper discusses the scheduling problem under the condition that the job processing time is a linear deterioration function of their start time. The makespan problems on the simple linear deterioration and on the general linear deterioration are considered respectively. The makespan problem on the simple linear deterioration is proved to be polynomial time solvable in this paper. The makespan problem on the general linear deterioration is, generally, not polynomial time solvable. In this paper, it is proved that there are two special cases which are polynomial time solvable.

Received: April 8, 2004

AMS Subject Classification: 90B35

Key Words and Phrases: scheduling, single machine, linear deterioration, makespan

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2004
Volume: 13
Issue: 4