An Algorithm Of Shortening Idle Time For Job Shop Scheduling Problems

The Job shop scheduling problem is a combinatorial optimum problem that is constrained with time,sequence and resource. It has been proved in theory that the Job shop scheduling problem is a classical NP problem. So the way of solving this problem is the research and application of excellent optimal scheduling algorithms.This paper divides the operations into the dependent operations that have the only immediate predecessor and immediate successor and the independent ones in common scheduling problems by analyzing the processing chart. Because the independent operations is parallel and the scheduling time is short and it is flexible, the research of scheduling the independent operations is important for shorten the total scheduling time. The method of scheduling the independent operations before is the best fit method, the paper analyzes the deficiency of the method and presents a new algorithm which is called shorting idle time in order to improve it. This algorithm schedules the independent operations and idle times which are on the critical machine by size respectively and according to the comparative result, the algorithm uses different methods to insert the independent operation to the corresponding idle time. This algorithm could reduce the total idle time of the machines and let the total scheduling time be less than the total scheduling time of the operations on the critical path and we can get better result if we use the algorithm to solve many static Job shop scheduling problems with the algorithm used before.The purpose of this paper is using the algorithm to solve the dynamic Job shop scheduling problems. The operations which have been scheduled are the end of the processing tree. That is, the operations which have not been scheduled are still the processing tree. During the processing of one job, if another job needs to be processed, we could schedule it with the mentioned method that solving static Job shop scheduling problem. So this algorithm can be use to solve the dynamic Job shop scheduling problems and it is proved to be practical and effective by examples.The algorithm of solving the common and dynamic Job shop scheduling problem is presented in the paper which has value both in practice and theory.