Complex scheduling problems in manufacturing and railroad industries
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
Min-You Wu Principal Investigator (2014-04-02)Static scheduling utilizes the knowledge of problem characteristics to reach a global optimal, or near optimal, solution. Although these scheduling algorithms apply to parallel programs, the algorithms themselves are ...
Wei Wennie Shu Principal Investigator (2014-04-02)In global parallel scheduling all processors cooperate to schedule work. This should be contrasted with dynamic scheduling since it generates a well-balanced load without incurring a large overhead. This project will explore ...
Tevfik Kosar Principal Investigator (2014-04-02)This project will further develop and enhance the Stork Data Scheduler to support Azure cloud computing environment, and to mitigate the end-to-end data handling bottleneck in data-intensive cloud computing applications. ...