Complex scheduling problems in manufacturing and railroad industries

Scheduling is a classical problem in manufacturing and logistics, and many practical versions are NP-hard. This dissertation studies two parallel machine scheduling problems and one crew balancing problem in detail.;The first model considers an assembly scheduling problem to minimize makespan in a manufacturing facility that consists of a number of work centers. Each work center consists of a number of identical parallel machines. The job to be processed via this facility is a job with tree-structure precedence constraints, and each operation has a designated work center. We propose a mixed-integer linear programming formulation and solve the problem with Lagrangian relaxation approach. After relaxation, the Lagrangian relaxation problem is decomposed into a number of subproblems. The subproblems are NP-hard and solved via a heuristic algorithm. Subgradient search is implemented for obtaining good values Lagrangian multipliers. Feasible solutions are obtained via a randomized list scheduling and lower bounds are generated by relaxing precedence constraints. Computational testing results show the algorithm could achieve near optimal solution within few seconds for problem size up to 8 machines and 300 operations.;The second model deals with an identical parallel machine scheduling with objective to minimize total weighted completion time and weighted makespan. The weights for operations can be positive, zero or negative. This problem comes from the subproblem of the first model. Column generation (CG) is implemented for solving this problem. In the column generation procedure, the pricing problem is NP-hard and solved approximately. Besides the original problem, we also test the performance of the CG procedure on objectives of minimizing makespan and minimizing total weighted completion time. The result shows that this procedure can obtain good solution for problems with size up to 20 machines and 200 operations.;The third model is an application of scheduling in railroad industry. A U.S. class I railroad corporation is facing with a problem of reducing crew deadhead operational cost. Under complex federal regulations, business rules and inaccurate information, crews are scheduled to cover trains. In the real application, this work is done manually and repositioning unbalanced crew movement lead to high cost. In this model, the whole railroad network is decomposed into a number of basic structures. Then, a concept of "virtual crew" is proposed to set up a mixed integer linear program for the basic structure. The computational results show that fast solutions exist for a basic unit in the railroad network, and the efficiency is adequate for the entire Eastern US network.