Research On Complex Product Integrated Scheduling Problem With Sequence-Dependent Setup Times

With the developing rapidly of information technology, continuously increasing trend of economic globalization and customer demand changing rapidly, enterprises set up an urgent claim to enhance the improvement and innovation of technology and management. The core of production management is whether the production plan scheduling problems can get the optimal solution, therefore the study of scheduling scheme has been the research focus of many scholars for many years at home and abroad.The scheduling problem with sequence-dependent setup times is that when the machine process different operations, it needs to be self-adjust, and setup times not only be related to the operation that will be process, but also be related to the operation that has been processed. There are a number of experts having studied on such issue. But the existing research of the scheduling with setup times can only solve the simple product scheduling problem with non-restraint among jobs and did not take into account the constraint among jobs. In this paper, the complex product integrated scheduling problem with sequence-dependent setup times (Referred to as complex product scheduling problem) is studied, which considers the constraint among jobs and considers the setup times for machine. So it has important theoretical and practical significance.For the scheduling problem with sequence-dependent setup times of complex single product, the algorithm that dynamically inserts the setup time in the process of scheduling operations is proposed. After the scheduling sequence of operations is determined, the starting time of each operation is determined by dynamically inserting setup time once. As the proposed algorithm avoids several movements of the scheduled operation when the setup time is inserted, the time complexity is sharply reduced.For the scheduling problem with sequence-dependent setup times of complex multi-product, the algorithm constructs the virtual manufacturing tree in the way of root alignment and converts the complex multi-product scheduling problem to the complex single product scheduling problem. Then the virtual single-product scheduling problem with sequence-dependent setup times is processed with the algorithm developed, and the scheduling problem with sequence-dependent setup times of complex multi-product is solved.For the dynamic scheduling problem with sequence-dependent setup times of complex product, a new virtual processing operation tree is constructed by the product remained and the dynamic arriving product. And the complex product dynamic scheduling problem with sequence-dependent setup times is converted into the virtual single product scheduling problem with sequence-dependent setup times. The virtual single product scheduling problem with sequence-dependent setup times is scheduled by the hierarchical algorithm proposed, and the complex product dynamic scheduling problem with sequence-dependent setup times is solved.