| Today many researchers attempt to solve Job-Shop Scheduling Problem (JSSP) by different methods. But because the problem is so complex that each method has its own shortage. For instance the method is more complex itself or the result is less optimized.In the dissertation a new algorithm for JSSP is designed which is modeled the advanced theories of process (thread) scheduling in operating system. Operations in JSSP have concurrence and synchronisms. To take good advantage of the characters of operations and resource (machine) are able to increase manufacturing efficiency and make the total manufacturing time less. Firstly a manufacturing tree is constructed according to job. Then theories of process (thread) scheduling in operating system are modeled and the priority of operation is set by operation's level. All operations are separated into non-schedulable operation and pre-schedulable operation and schedulable operation. An operation collection for scheduling is generated. Except in the condition that some working procedures need dynamic adjusting, from the very beginning to the end one principle must be followed that is to keep the machine busy, which means that the job is dispatched to the machine incessantly so long as the machine is idle. When scheduling operation, some operation is selected from operation collection and scheduled to a machine. When selecting operation, four strategies must be followed. After an operation is selected, the node of the operation is deleted from manufacturing tree and then a new operation collection is generated again. When the collection is empty, the job is finished. A method of constructing virtual manufacturing tree for multi-job JSSP or dynamic JSSP is designed and the problem is simplified. When scheduling, operation is scheduled from virtual manufacturing tree by the four strategies. By instance and comparison the algorithm has satisfied complex and can get good result. So the algorithm has important value both in practice and theory. |
PDF Full Text Request