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 ...
The Effects of New Bus Designs on Bus Dwell Time and Bus Schedule Adherence when used by Passengers with Mobility Limitations: An Integrated Approach with Human Subject Experiments and Microscopic Traffic Simulation Mahdavilayen, Milad (State University of New York at Buffalo, 2019)Both Bus dwell time and bus headway adherence are critical to the serviceability of bus transit system. It is acknowledged that passengers with physical disabilities will greatly impact the bus dwell time and bus headway ...
Chen, Zhenming (2007)Scheduling problem is a fundamental and versatile problem in theoretical computer science. It has been extensively studied in many different variations. Most of existing scheduling models only deal with one type of resources, ...