Study On Bottleneck-based Decomposition Procedure For Large-scale Production Scheduling Problems

IIIProduction scheduling problem is to optimally allocate manufacturing machines to competitive jobs over time. Due to its important practical value and NP-hard characteristic, it draws high attention of manufacturers and academe. With the problem size and complexity increasing, the large-scale complex production scheduling has become one of the hardest problems in manufacturing system. It is difficult in modeling and optimization. The decomposition method is a generic approach to solve the large-scale production scheduling problem. However, it may lead to a local optimum and has a low convergence speed. Although some bottleneck scheduling methods have been studied to deal with the problem from the viewpoint of global optimization, the research is elementary and limited. There still exist large spaces in both the theoretical study and practical application. In this thesis, the bottleneck-based decomposition method for large-scale complex production scheduling problems is studied.The main research works of this dissertation are as follows.Based on the decomposition theory, the machine-based decomposition method for production scheduling problems is analyzed and its shortcomings are pointed out. By utilizing the bottleneck property in the unbalanced production line, the generic framework of the bottleneck-based decomposition procedure is proposed. This procedure combines bottleneck theory with decomposition method. Then its key techniques are given.For the flow shop problem with one bottleneck machine, a bottleneck-based decomposition procedure is proposed. In this method, the machines on the flow shop are divided into a bottleneck machine, upstream and downstream non- bottleneck machines. By relaxing the capacity constraints of non-bottleneck machines, the flow shop problem is reduced into a single-machine scheduling problem. The bottleneck scheduling can be obtained by solving the reduced problem optimally. While the upstream non-bottleneck machines are scheduled backward based on the bottleneck scheduling, and the downstream non-bottleneck machines are scheduled forward based on the bottleneck scheduling. Then we give some conditions to describe the redundant capacities of the non-bottleneck machines, and prove that the optimal scheduling to the flow shop is a permutation scheduling under these conditions. In other words, the sequence of jobs on each non-bottleneck machine is the same as that of jobs on the bottleneck machine. Computational results show that the bottleneck-based decomposition algorithm can obtain a good solution in quite short time.For the job shop problem with one bottleneck machine, a bottleneck-based decomposition procedure is proposed. In this method, the machines on the job shop are divided into a bottleneck machine and non-bottleneck machines based on the bottleneck property. Under the assumption that the capacities of non- bottleneck machines are infinite, operations on the non-bottleneck machines are aggregated into a time delay. The job shop problem is then reduced into a single-machine scheduling problem with release time and delivery time constraints. The bottleneck scheduling can be obtained by solving the reduced problem optimally, while the non-bottleneck machines are scheduled around the bottleneck scheduling by some effective dispatching rules. The conflict between the scheduling of the bottleneck machine and non-bottleneck machines can be coordinated by adjusting the release times and delivery times of operations on the bottleneck machine. Computational results show that the bottleneck-based decomposition procedure can obtain a good solution for the job shop problem with high bottleneck degree.For the unbalanced job shop problem with multiple constraint machines (JSPMC), a constraint scheduling procedure is proposed. In this procedure, a new strategy is given to identify the constraint machines iteratively. At each iterative procedure, the non-constraint machines are scheduled with an effective dispatching rule, and a constraint machine is identified based on the scheduling results of the non-constraint machines. This procedure continues until no constraint machine is identified. Then the constraint machines can be formulated as a multiple-machine scheduling problem with time lags. Its solution provides a low bound for the JSPMC. In addition, we prove that the low bound increases iteratively with the set of constraint machines increasing, and it is close to the optimal solution of the JSPMC. Extensive computational results indicate that the proposed constraint scheduling algorithm can obtain a better tradeoff between solution quality and computation time comparing with various versions of the shifting bottleneck (SB) methods for the JSPMC. For the larger scale job-shop problem, which is difficult to be solved by the constraint scheduling procedure, we propose a bottleneck-based rolling scheduling method based on the bottleneck and temporal decomposition strategies. In this method, the scheduling horizon is divided into some smaller time windows. The subproblem to each time window is still a job shop problem, which can be solved by the constraint scheduling procedure. Since the large-scale problem is divided in the level of space and time, it provides a new idea to solve large-scale job shop scheduling problem. Computational results show that the method is effective.The bottleneck-based rolling scheduling procedure is applied to a more complex job shop problem, i.e. semiconductor manufacturing process. Since the workcenters in the semiconductor manufacturing process are different, various solution procedures are given to solve their corresponding subproblems. At last, this method is tested in a classic MINIFAB model.