Study Of Bottleneck Problem In Job-Shop Scheduling

Job-Shop scheduling problem is the most difficult production problem which is the most complicated and common. General Job-Shop scheduling problem assumes that every machine is single, so there is usually certain kind of device which affects the total processing time of production most and becomes scheduling bottleneck of the whole production processing. The method for solving such instance is usually to get the processing sequence of every operation. Adding the bottleneck device is a simple method for solving bottleneck problem. Now the conception of bottleneck has not been well understood, and there have not been perfect methods for defining bottleneck in academia and in practice, but the key problem of Job-Shop scheduling bottleneck problem is not only to find the bottleneck device but also to confirm that it is such an increasable device that the processing efficiency can have an impressive promotion after a same device is added.Firstly, an accurate and fast method for judging parallel operations is put forward by studying parallel operations. The first step is to name all routes from every leaf to the root with different numbers in the production processing tree.All nodes are searched and marked the numbers of their relevant routes. The second step is to judge parallel operation. If two nodes have one or more same numbers, the two operations relevant to the two nodes will have the constraint of predecessor and successor, and they can not be processed currently. If their numbers are completely different, the two operations relevant to the two nodes will have no the constraint of predecessor and successor, and they can be processed currently. Secondly, the algorithm of confirming the increasable bottleneck device based on parallel operations is presented. The total processing time of parallel operations and the total number of parallel operations for every device will be gotten, and the device with the longest total processing time of parallel operations will be the increasable bottleneck device. In an interconnected production system, machines block and starve each other. The longer a machine is active without interruption, that is to say, the processing state, the more probable it is that this machine blocks or starves other machines; because the operation processed is possibly the immediate predecessor of other operations on other device. Then a method which takes immediate predecessor into account is put forward. Finally, the problem that is to find the increasing bottleneck device in dynamic Job-Shop scheduling is studied.The method presented offers new research thought for the bottleneck of Job-Shop scheduling problem, which has important value both in practice and theory.