|
Graduation Thesis from 2008
Lee, Kwang Bok
M.S. |
Heuristic Algorithms for the Mixed-Model Disassembly-Line Balancing Problem During the last decades, growing concerns on environmental issues have enforced the industry to develop environmentally conscious products and their processes. Among others the disassembly process, one of the elements in product recovery system, was the most based on in the product process system. This dissertation considers the line balancing problem for designing disassembly systems called the disassembly line balancing problem (DLBP) in the literature. For a given disassembly process plan that specifies all parts and components together with necessary disassembly tasks, the DLBP is to assign individual disassembly tasks to workstations while satisfying the precedence relations among tasks. As an extension of the existing research, this dissertation considers a mixed-model version of the DLBP since multiple used or end-of-life products are usually disassembled in ordinary disassembly systems. The objective is to minimize the number of workstations. A 0-1 integer programming model is presented to describe the problem mathematically. Since the problem considered in this dissertation is NP-hard, this dissertation suggests several simple heuristic algorithms in which disassembly tasks are ordered using a certain priority rule and then they are assigned to workstations according to this order while considering a given cycle time and precedence relations among tasks. Computational experiments were done on a number of test problems up to 500 tasks, and the results are reported. In particular, some of the heuristics gave the near optimal solutions for most small-size test problems. |
Kim, Hyeok Chol
M.S. |
A Case Study on Capacitated Lot-sizing and Scheduling in a Paper Remanufacturing System We consider the capacitated lot-sizing and scheduling problem for a paper remanufacturing system that produces several types of corrugated cardboards. The problem is to determine the lot sizes as well as the sequence of lots for the objective of minimizing the sum of setup and inventory holding costs while satisfying the demand and the machine capacity over a given planning horizon. In particular, the paper remanufacturing system has sequence-dependent setup costs that depend on the type of product just completed and on the product to be processed. Also, the setup state at one period can be carried over to the next period. An integer programming model is presented to describe the problem. Due to the complexity of the problem, we suggest two-stage heuristic algorithms in which an initial solution is obtained and then it is improved using a multi-pass interchange method. To show the performances of the heuristic algorithms, computational experiments were done using the real data, and a significant amount of improvement is reported. |
Kim, Hyung Won
M.S. |
Scheduling Algorithms for Hybrid Flow Shops with Reentrant Flows and Unrelated Parallel Machines This thesis considers the scheduling problem in reentrant hybrid flow shops with parallel machines at each serial production stage. In reentrant hybrid flow shops, each job may visit each production stage several times, called the reentrant product flows in the literature. As an extension of the existing research, we consider the unrelated parallel machines at each stage and hence the processing times of a job depends on the machine where the job is processed. The problem is to determine the allocation of jobs to unrelated parallel machines as well as the sequence of the jobs assigned to each machine for the objectives of minimizing makespan and total tardiness. Since due-dates must be satisfied after negotiated with customers in most practical situations, the problem is transformed into the one with a single objective of minimizing makespan by moving the tardiness objective to a constraint set with a certain allowance. Due to the complexity of the problem, two heuristics are suggested and tested in this thesis. In particular, the two heuristics are competitive to a search heuristic with sufficiently long computation time. |
|
