|
Graduation Thesis from 2009
Kim, Jun Kyu
Ph.D. |
Common Due-Date Assignment and Scheduling in Single and Parallel Machines with Sequence Independent and Dependent Setup Times This dissertation focuses on common due-date assignment and scheduling problems with sequence independent and dependent setup times. Assigning due-dates has a certain practical implication when a company offers due-dates to its customers' orders during sale negotiations or a sales person offers a price reduction when due-dates are far away from the expected ones. In fact, there may be various situations in which due-dates are negotiated rather than simply set by customers. In the first chapter, we consider the problem on single machine for the objective of minimizing the sum of the penalties associated with assigning the common due- date, earliness, and tardiness. Unlike the previous research articles on the single machine problem, we consider sequence dependent setup times that make the problem much more difficult. Although the sequence-dependent setup is one of important concerns in real production systems, it makes the problem much more complicated. To solve the problem, a branch and bound algorithm, which incorporates the method to obtain lower and upper bounds as well as a dominance property to reduce the search space, is suggested that gives the optimal solutions for small-sized instances. Also, heuristic algorithms are suggested to obtain solutions for large-sized problems within a reasonable computation time. The performances of the algorithms, computational experiments on randomly generated test instances and results are reported. In addition, we report a case study in a paper remanufacturing system that produces corrugated cardboards using waste papers under the make-to-order environment. Since the system produces corrugated cardboards in an integrated process and has sequence-dependent setup times, we adopt the solution algorithms for the single machine problem considered in this chapter. In the objective function, the penalties associated with earliness and tardiness can be obtained from inventory holding and backorder costs, respectively. Computational experiments were done on the case data and the results are reported. In the second chapter, we consider the problem on parallel machines with sequence-independent setup times. The main decisions are: (a) fixing the common-due-date; (b) allocating jobs to parallel machines; and (c) sequencing the jobs assigned to each machine. The objective is to minimize the sum of the penalties associated with assigning the common due-date, earliness, and tardiness. Due to the complexity of the problem, we suggest two types of heuristics, a two-stage heuristic and search heuristics, after characterizing the solution properties. The two-stage heuristic, which is useful when computation time is critical, solves the problem with two stages: obtaining an initial solution and improvement. The search heuristics, tabu search and simulated annealing algorithms, are based on the neighborhood generation methods devised for the problem. Computational experiments were done on a number of test problems and the results show that both types of algorithms outperform the existing ones, respectively. The last chapter extends the problem considered in the second chapter by considering sequence-dependent setup times. Since it is not appropriate to develop optima1 algorithm, we suggest heuristic algorithms in which an initial solution is obtained and then it is improved. Computational experiments were done on a number of test problems and the results are reported. |
Choi, Hyun Seon
Ph.D. |
Scheduling Algorithms for Unidirectional and Reentrant Hybrid Flow shops This dissertation focuses on scheduling problems in hybrid flow shops that consist of two or more production stages in series, but there exist one or more parallel machines at each stage. The parallel machines are added to each stage for the objective of increasing productivity as well as flexibility. The hybrid flow shops can be found mainly in the electronics industry such as printed circuit board manufacturing, semiconductor manufacturing, and lead frame manufacturing. Also, various traditional industries, such as food , chemical and steel, have hybrid flow shops. According to product flows, the hybrid flow shops can be classified into two types: (a) those with unidirectional flows; and (b) those with reentrant flows. The unidirectional flows imply that each job starts at the first stage and finishes at the last stage. On the other hands, in the reentrant flows, each job may visit (enter) each serial stage two or more times. In this dissertation, we consider the scheduling problems in unidirectional and reentrant hybrid flow shops.
First, we consider the two-stage unidirectional hybrid flow shop scheduling problem for the objective of minimizing the number of tardy jobs. Each job is processed through the two production stages in series, each of which has multiple identical parallel machines. The problem is to determine the allocation of jobs to the parallel machines as well as the sequence of the jobs assigned to each machine. To solve the problem, a branch and bound algorithm, which incorporates the methods to obtain the lower and upper bounds as well as the dominance properties to reduce the search space, is suggested that gives the optimal solutions. In addition, two-phase heuristic algorithms are suggested to obtain good solutions for large-size problems within a reasonable amount of computation time. To show the performances of the optimal and heuristic algorithms suggested in this chapter, computational experiments are done on a number of randomly generated test problems, and the test results are reported.
Second, we consider the scheduling problem in two-stage reentrant hybrid flow shops in which each job has reentrant flow, i.e., the job visits each production stage several times. The objective is to minimize makespan subject to the maximum allowable due-dates in the form of a constraint set with a certain allowance. To solve the problem, two types of algorithms are suggested: (a) a branch and bound algorithm that gives optimal semi -permutation schedules; and (b) heuristic algorithms that give non-permutation schedules. Computational experiments were done on a number of test problems and the results show that one of the heuristics is competitive to the branch and bound algorithm with respect to the solution quality while requiring much shorter computation times.
Third, as an extension of the first problem, we consider the scheduling problem in multi-stage unidirectional hybrid flow shops for the objective of minimizing the number of tardy jobs. Due to the complexity of the problem, we suggest search heuristics that incorporate a new method to generate neighborhood solutions. In particular, to evaluate and select neighborhood solutions, three surrogate objectives are additionally suggested because not much difference in the number of tardy jobs can be found among the neighborhoods. To test the performances of the search heuristics, computational experiments were performed on a number of test problems and the results show that the search heuristics with surrogate objectives were better than the original ones. Also, they gave the optimal solutions for most small-size test problems.
Finally, as an extension of the second problem , we consider the scheduling problem in multi-stage reentrant hybrid flow shops. Unlike the theoretical approach on reentrant hybrid flow shop scheduling, we suggest a real-time scheduling mechanism with a decision tree when selecting appropriate dispatching rules. Here, the decision tree, one of the commonly used data mining techniques, is adopted to eliminate the computational burden required to carry out simulation runs to select dispatching rules. To illustrate the mechanism suggested in this study, a case study was performed on a thin film transistor-liquid crystal display (TFT-LCD) manufacturing line and the results are reported. |
Doh, Hyoung Ho
M.S. |
Production Planning in Remanufacturing Systems: Mathematical Model and Solution Algorithms Remanufacturing, one of the most advanced product recovery options, processes used or end-of-life products with disassembly, reprocessing, and reassembly operations in such a way that their qualities are as good as new in terms of appearance, reliability, and performance. Among various issues in remanufacturing, we focus on production planning over a given planning horizon for the objective of maximizing the total profit, i.e., difference between the revenues and relevant costs. The main decisions are: (a) number of products to be disassembled and disposed in each period; (b) number of parts and components to be reprocessed and disposed in each period; (c) number of parts and components to be purchased in each period; and (d) number of products to be reassembled in each period. In particular, we extend the existing model by incorporating setup costs and times. A mixed integer programming model is developed to represent the problem. Then, due to the complexity of the problem, heuristic algorithms, based on the linear programming-based technique, are suggested in this paper. Computational experiments were done on various test problems, and the results are reported. |
Yu, Jae Min
M.S. |
Scheduling Algorithms for Job Shops with Job Families: Minimizing the Sum of the Maximum Family Flow Times This paper addresses the scheduling problem for job shops in which jobs are grouped into job families for further assembly operations, but processed individually. The job shops considered in this paper can be found in various production systems, especially in remanufacturing shops that process parts or components obtained after disassembling used or end-of-life products. The main decision is the sequence of the jobs assigned to each machine, which is the same as that of the ordinary job shop scheduling problem. To minimize the deviations of the job completion times within each job family, the objective is set to minimizing the sum of the maximum family flow times. To describe the problem mathematically, an integer programming model is presented. Then, we suggest 2-phase methods: (a) obtaining initial solutions using priority rules based heuristics, (b) neighborhood generation methods for improvement Computational experiments were performed on various test problems and the results are reported. |
Ma, Yoen Seok
M.S. |
A Disassembly Process Planning Algorithm for End-of-Life Products Recovery and Environmentally Conscious Disposal Disassembly process planning is an act of preparing detailed operation instructions for disassembling an end-of-life product to recover or dispose its constituent parts or subassemblies. The main decisions are: (a) disassembly level; (b) disassembly sequence; and (c) end-of-life options such as reuse, remanufacturing, recycling, incineration, landfill, etc. This paper deals with the three decision variables simultaneously in the parallel disassembly environment for the objective of maximizing the profit. Unlike previous research studies, we consider practical constraints, i.e., reuse probability and environmental impacts of parts or subassemblies, sequence-dependent setup costs, regulation on recovery rate, and incineration capacity. To represent and solve the problem, we develop an extended AND/OR graph, and then suggest a two-phase algorithm. To show the effectiveness of the proposed algorithm suggested in this paper, a case study has been carried out on an automatic pencil. Also, additional tests on other general product structures are also reported. The test results show that the algorithm suggested in this study good quality solutions within a reasonable amount of computation time for the test instances. |
|
