Solution approaches to large-scale production scheduling problems.

摘要

Production scheduling plays an important role in supply chain management for many businesses nowadays. Many manufacturers are facing difficulties finding proper assignments of their limited resource to a huge number of tasks. Effective and efficient solution approaches are required for solving these production scheduling problems.; In this thesis, we address two popular scheduling problems. One is the general single-machine earliness-tardiness (E-T) scheduling problem with distinct release dates, due dates, and unit costs. We aim to find an exact nonpreemptive solution in which machine idle time is allowed. We propose new solution approaches which hybridize dynamic programming (DP) and branch-and-bound (BB) techniques. We conducted computational experiments with randomly generated test instances in order to evaluate the effectiveness of these two approaches. The results clearly show that our new approaches can solve all the instances with up to 40 jobs and most of the instances with 50 jobs, which outperforms those approaches frequently used in scheduling research.; The other type of scheduling problem is a large-scale extended job shop scheduling problem. The classical job shop scheduling model is usually not applicable for real shop floor manufacturing. Besides the job precedence and the machine capacity constraints, our problem also includes the bill of material and the working shifts constraints. We first formulate the problem using a Mixed Integer Programming (MIP) model, and further obtain the problem's lower bound. We propose three solution approaches for this problem: dispatching rules, application of the Nested Partitions (NP) Framework, and a hybrid approach of dispatching rules and NP method. We also develop a sampling approach to sample from each subregion, so that every feasible solution in the subregion has a positive probability of being selected. Furthermore, weighted sampling approach is also presented to efficiently search in each subregion. Numerical results show that NP and its hybrid method significantly improve the solutions for most of the testing instances from the real industry.