Scheduling On Deterioration Of Processing Time

This paper discusses scheduling about deterioration of processingtime on single processor. It includes two kinds of model: if the jobprocessing time is an increasing function of its start time, it is called thefirst kind of deterioration problem; if the job processing time is anincreasing function of its position in the sequence, it is called the secondkind of deterioration problem.As to the first kind of deterioration problem, the linear increasingprocessing time function of its start time is discussed in this paper. It isproved that the problem is polynomial time solvable in some specialcases. When the problem can't be proved to be polynomial time solvable, polynomial time approximation algorithm is given.The second kind of deterioration problem to minimize makespan andtotal completion time is polynomial time solvable. It is proved that theproblem is identical to Assignment Problem, so it can be solved byHungarian method.