Single Machine Scheduling Problem With Start Time Dependent Processing Times

Scheduling problem is a kind of important combination optimization problem. In this thesis, we study the single machine step-deterioration scheduling problem and the single machine deteriorating scheduling problem with resource constrain. This thesis consists of two parts: the single machine step-deterioration scheduling problem; the single machine deteriorating scheduling problem with resource constrain.In the second chapter, we discuss the single machine step-deterioration scheduling problem. We study the optimal properties of the problem 1 |p_j=a or a+b_j, d |∑w_jC_j and according to it a kind of GA implement and a kind of Branch and Bound method are given. The given Branch and Bound method can find out the optimal solution of the problem in small size while the given GA implement can quickly find out the approximate optimal solution of the problem in large size. The given GA implement proves to be very effective by numerical experiments and examples. In the third chapter, we discuss two classes of single machine deterioration scheduling problem with resource constrain. One class is the mentioned problem in which the resource amount satisfies a certain condition and the goal is to minimize the makespan: the problem 1 |p_j = b_j t_j - a_j u_j ,∑u_j≤u|C max and the problem 1 |p_j = s_j + bt_j - a_j u_j ,∑u j≤u|C max. We provide the optimal resource allocations to anygiven sequences and the polynomial algorithms under certain conditions of the two problem; the other one is the mentioned problem in which the makespan satisfies a certain condition and the goal is to minimize the total resource amount: the problem 1 |p_j = b_j t_j - a_j u_j , C max≤C|∑u_j and the problem 1 |P_j = S_j + BT_j - A_j U_j , C max≤C|∑U_j As to the two problems, we respectively give the polynomial algorithm to any given sequence and two heuristic algorithms.