Study Of Multi-Equipment Compact Algorithm In Complex-Product's Scheduling Problem

In theory, Job Shop Scheduling Problem (JSSP) is among the hardest combinatorial optimization problems, it can be described as under some constraints and try to get the best result of the aim-function. In reality, the scheduling of resources on a large scale is to be one important factor which constraints the development of product. So the research on JSSP has important theoretical and applied significance.A flaw of classic JSSP is that hasn't enough consideration of real situation, ignoring the scheduling environment,scheduling object and scheduling equipments. In real producing there are complex-products which can be assembled by multi-job, each job can be assembled by multi-smaller-job, assembly is considered as an operation here, so the complex-product can be expressed as the processing and assemble of multi-job.In this paper, Multi-Equipment compact algorithm in Complex-Product's scheduling problem is studied thoroughly; the innovation is mainly in improving the efficiency of equipments. Firstly, in this paper, considering that the scheduling object is complex-product, a tree model for complex-product is built and detail description of the tree model is given. Secondly, aiming at the method key-equipment compact hasn't considered other equipments'compact, with considering all equipments'compact, a method based on multi-equipment compact is presented to improve the efficiency of all equipments. And the method of stretch in key-equipment compact is moving all correlated operations, which includes moving some not necessary operations, a method to determine the condition of stretching idle-time partition and the definition of pre-influence-set is proposed, under the condition stretching the idle-time partition and adjusting the pre-influence-set, so it avoids the moving of those not necessary operations, and makes all the equipments as compact as possible. At last, based on the Multi-Equipment compact, it further consider the forward moving of some operations after stretching and the stretching of non-idle time partition. The analysis of some complex-product examples shows that multi-equipment compact algorithm has absolutely advantage in improving the utilization of equipments and has a favorable complexity.