Scheduling Problem Under Linear Deteriorating Processing Time

Scheduling is an important combinatorial optimization problem. In the classical sche- duling it is usually assumed that the processing times of the tasks are constant values. However, the phenomenon that the processing time of the task is increased with its starting time delayed often occurs in many practical situations. In this paper, the scheduling of linear deteriorating processing time is studied by breaching the constant restriction of the processing times of the tasks in the classical scheduling. The models are more complex than classical scheduling problems, most of which are NP-hard problems. The main contri- butions in this paper can be summarized as follows:1. Minimize the total weighted completion time single machine scheduling problems. Under the simple linear deteriorating, according to the priority rule of the key task with parallel chains constraints tasks, the priority rule of the maximal family tree with tree precedence constraints is presented. Moreover, the optimal polynomial algorithms with the time complexity of O ( n2)are given. For the simple linear deteriorating model with gener- al precedence constraints, some properties are obtained, furthermore, an approximate alg- orithm is constructed.2. Minimize the makespan parallel machine scheduling problems. The NP-hard proble- m P 2 |p j =αj S j|Cmaxis proved by subset production problem in this paper. Under the simp- le linear deteriorating, the problem of identical processor is extended to uniform processor case, for the problem Qm |p j=αjS j| Cmax, the two heuristic algorithms with the time complexity of O (n)and O ( n2)are given respectively and the absolute performance ratio of the two algorithms are analysed.3. Minimize the makespan flow shop scheduling problems. Under the simple linear deteriorating, nonnegative start and stop lag deteriorating rates are introduced so as to construct composite jobs satisfying precedence relations. Based on those, the optimal polynomial algorithms are given for the two-machine flow shop scheduling problem with the simple linear deteriorating model with chains and series-parallel digraphs precedence constraints jobs respectively. For the NP-hard problem F 2 | pi j = Xij+αijSij| C max, by defi- ning dominating relations among procssors, the polynomial algorithms are given under the dominating procssors respectively for the general linear deteriorating the flow shop sched- uling problem Fm | pij = Xij+αijSij|Cmax.