PLI Laboratory | Hanyang University

Graduation Thesis from 2006

Kim, Sang Il
M.S.

Search Heuristics for Parallel Machine Scheduling with Sequence-Dependent Setup and Ready times: Minimizing Total Tardiness

This thesis considers the problem of scheduling a set of independent jobs on parallel machines for the objective of minimizing total tardiness. Each job may have sequence-dependent setup and distinct ready times, i.e., the time at which the job is available for processing. These make the parallel machine scheduling problem considered in this thesis more difficult than the ordinary ones. Due to the complexity of the problem, two types of search heuristic, tabu search and simulated annealing, are suggested that incorporate new methods to generate the neighbourhood solutions. Three methods of obtaining the initial solutions are also suggested. Computational experiments are done on a number of randomly generated test problems, and the results show that the search heuristics suggested in this thesis outperform the existing one.

Park, Sang Hyun
M.S.

Scheduling Algorithms for Multiple Arc-Welding Robots Considering Thermal Distortion

This thesis focuses on a scheduling problem in multiple arc-welding robot systems, which is the problem of assigning welding operations to robots as well as determining their sequences for the objective of minimizing the maximum completion time. Each welding operation is denoted by a weld line with two end points, each of which can be a possible start point to perform the welding operation. Heat-caused distortion is explicitly considered in the form of delay between welding operations associated with weld lines near each other. Due to the complexity of the problem , this thesis suggests three types of search heuristic, genetic algorithms, simulated annealing algorithms and tabu search algorithms, each of which incorporates new methods to generate neighbourhood solutions. To show the performances of the heuristics, computational experiments are performed on a number of randomly generated test problems and the results are reported.

Jeon, Hyong Bae
M.S.

A Study on Capacitated Disassembly Scheduling Problems

For the last decades, growing concerns on environmental issues have stimulated the industry to develop various material and product recovery processes. Disassembly, one of the essential material and product recovery processes, is the process of separating used or end-of-life products into their constituent parts, subassemblies, or other groupings. Due to its importance in material and product recovery, previous research has been done on various disassembly roblems such as design for disassembly, disassembly process planning, disassembly scheduling and so on. In this dissertation, we focus on disassembly scheduling problem which is generally defined as the problem of determining the quantity and timing of disassembling used or end-of-life products while satisfying the demand of their parts and/or components over a planning horizon. The case of assembly product structure is considered, and two problems having different objective function are presented. In particular, most previous research on disassembly scheduling is uncapacitated one, but the resource capacity constraints are explicitly considered in this dissertation. Firstly, we present the problem with the objective of minimizing the number of products to be disassembled, which is the basic case of capacitated disassembly scheduling problem. To define the problem formally, we formulate it as an integer programming model. After deriving some properties, an optimal algorithm consisted of two stages is developed. Computational experiments are done intensively on randomly generated problems, and the result shows that the algorithm can give an optimal solution within a very short computation time. Secondly, as the extension to the problem presented previously in this dissertation, we present the problem with the objective of minimizing the sum of disassembly operation and inventory holding costs. The problem is formulated as integer programming model, too. And then a two-stage heuristic with construction and improvement algorithms is suggested in this dissertation. To test the performance of the heuristic algorithm, co mputational experiments are done using the same manner to the case of the first problem, and it reveals that the heuristic gives a near optimal solution within a very short amount of computation time. In fact, the problems considered in this dissertation can be solved using commercial software packages. But generally, they consume excessive computation time inconsistently. While, the algorithms suggested in this dissertation can give an (near) optimal solution within a very short computation time consistently. And in the practical sense, the algorithms of this dissertation give more applicable solution in real world by conside ring capacity limitations. Part commonality and various uncertain factors, i.e., defectiveness and stochastic demand, can be considered in the problems of future researches.