Batch Scheduling Problem And Resource Constrained Scheduling Problem

Scheduling problem is an important combination optimization problem. In this thesis, we study problems of batching scheduling, flow shop with group technology, resource constrained scheduling. We will discuss the scheduling problem in three parts: the model of batch scheduling with arrival time; the polynomial algorithm of flow shop scheduling problem with time lag between process and with group technology; three optimal algorithms of resource constrained scheduling problems.In the second chapter, a 0-1 integer programming model is formulated for the scheduling problem with release time on single batch processing machine minimizing completion timel |B,r_j| C_max . According to this model numerical tests are made and the sizes of computable instances are obtained with LP process of statistics software SAS.In the third chapter, we study flow shop scheduling problem with time lag between two processes and with group technology minimizing completion time F2 | s_ij GT |C_max. It is proved that there exits a polynomial algorithm for two-machine problems.The fourth chapter discusses two resource allocation problems in single machine scheduling with arrival times 1| r_j , p_j = b_j-a_j u_j , C_max≤ C | ∑u_j and 1|r_j prec P_j=b_j-a_ju_j, C_max ≤c|∑u_j ,and a discretely-divisible resource constrained scheduling problem P2 |res... ,P_j=a,2a | C_max (the job of which processing time is same can not be processed in the machine simultaneously). It is proved that there exit three polynomial algorithms for these problems.