Heuristic approaches for the U-line balancing problem.

Ho Kin Chuen Matthew.Thesis (M.Phil.)--Chinese University of Hong Kong, 1998.Includes bibliographical references (leaves 153-157).Abstract also in Chinese.Chapter 1 --- Introduction --- p.15Chapter 1.1 --- The U-line Balancing Problem --- p.15Chapter 1.2 --- Configuration of an U-line --- p.17Chapter 1.3 --- Feasible subsets and sequences --- p.19Chapter 1.4 --- Assignment of tasks to stations --- p.21Chapter 1.5 --- Costs --- p.22Chapter 1.6 --- Formulation of The U-line Balancing Problem --- p.23Chapter 1.7 --- Design of computational study --- p.25Chapter 1.7.1 --- Input parameters --- p.25Chapter 1.7.2 --- Output variables --- p.26Chapter 1.7.3 --- Problems solved --- p.27Chapter 1.7.3.1 --- Problem Set One --- p.28Chapter 1.7.3.2 --- Problem Set Two --- p.28Chapter 1.7.3.3 --- Problem Set Three --- p.29Chapter 1.7.3.4 --- Problem Set Four --- p.29Chapter 1.8 --- Contributions --- p.29Chapter 1.9 --- Organization of thesis --- p.30Chapter 2 --- Literature Review --- p.31Chapter 2.1 --- Introduction --- p.31Chapter 2.2 --- The Straight-line Balancing Problem --- p.32Chapter 2.2.1 --- Single-model Assembly Line Balancing with deterministic task time (SMD) --- p.34Chapter 2.2.2 --- Single-model Assembly Line Balancing with stochastic task times (SMS) --- p.36Chapter 2.2.3 --- Multi/Mixed-model Assemble Line Balancing with deterministic task times (MMD) --- p.37Chapter 2.2.4 --- Multi/Mixed-model Assembly Line Balancing with stochastic task times (MMS) --- p.38Chapter 2.3 --- The U-line Balancing Problem --- p.39Chapter 2.4 --- Conclusions --- p.45Chapter 3 --- Heuristic Methods --- p.47Chapter 3.1 --- Introduction --- p.47Chapter 3.2 --- Single-pass heuristic methods --- p.47Chapter 3.3 --- Computational results --- p.50Chapter 3.3.1 --- Problem Set One --- p.50Chapter 3.3.2 --- Problem Set Two --- p.52Chapter 3.3.3 --- Problem Set Three --- p.54Chapter 3.3.4 --- Problem Set Four --- p.55Chapter 3.4 --- Discussions --- p.57Chapter 3.5 --- Conclusions --- p.59Chapter 4 --- Genetic Algorithm --- p.60Chapter 4.1 --- Introduction --- p.60Chapter 4.2 --- Application of GA to The Straight-line Balancing Problem --- p.61Chapter 4.3 --- Application of GA to The U-line Balancing Problem --- p.62Chapter 4.3.1 --- Coding scheme --- p.63Chapter 4.3.2 --- Initial population --- p.64Chapter 4.3.3 --- Fitness function --- p.65Chapter 4.3.4 --- Selection scheme --- p.66Chapter 4.3.5 --- Reproduction --- p.67Chapter 4.3.6 --- Replacement scheme --- p.68Chapter 4.3.7 --- Elitism --- p.68Chapter 4.3.8 --- Termination criteria --- p.68Chapter 4.4 --- Repair method --- p.69Chapter 4.5 --- Crossover operators --- p.71Chapter 4.5.1 --- Sequence and configuration infeasible crossover operators --- p.72Chapter 4.5.1.1 --- Partially Mapped Crossover (PMX) --- p.72Chapter 4.5.1.2 --- Order Crossover #1 (ORD#l) --- p.74Chapter 4.5.1.3 --- Order Crossover #2 (ORD#2) --- p.74Chapter 4.5.1.4 --- Position Based Crossover (POS) --- p.75Chapter 4.5.1.5 --- Cycle Crossover (CYC) --- p.76Chapter 4.5.1.6 --- Edge Recombination Crossover (EDG) --- p.77Chapter 4.5.1.7 --- Enhanced Edge Recombination Crossover (EEDG) --- p.80Chapter 4.5.1.8 --- Uniform-order Based Crossover (UOX) --- p.81Chapter 4.5.2 --- Sequence feasible but configuration infeasible crossover operators --- p.82Chapter 4.5.2.1 --- One-point Crossover (1PX) --- p.82Chapter 4.5.2.2 --- Two-point Crossover (2PX) --- p.84Chapter 4.5.2.3 --- Uniform Crossover (UX) --- p.85Chapter 4.6 --- Mutation operators --- p.86Chapter 4.6.1 --- Sequence infeasible mutation operators --- p.87Chapter 4.6.1.1 --- Inversion (INV) --- p.87Chapter 4.6.1.2 --- Insertion (INS) --- p.87Chapter 4.6.1.3 --- Displacement (DIS) --- p.88Chapter 4.6.1.4 --- Reciprocal Exchange (RE) --- p.88Chapter 4.6.2 --- Sequence and configuration feasible mutation operators --- p.89Chapter 4.6.2.1 --- Scramble Mutation (SCR) --- p.89Chapter 4.6.2.2 --- Feasible Insertion (FINS) --- p.90Chapter 4.7 --- Computational study --- p.91Chapter 4.7.1 --- Comparison of crossover operators --- p.91Chapter 4.7.2 --- Comparison of mutation operators --- p.95Chapter 4.7.2.1 --- Order crossover#2 and mutation operators --- p.95Chapter 4.7.2.2 --- Position based crossover and mutation operators --- p.97Chapter 4.7.3 --- Parameters setting --- p.99Chapter 4.7.4 --- Computational results --- p.104Chapter 4.7.5 --- Comparative results --- p.105Chapter 4.7.5.1 --- Problem Set One --- p.105Chapter 4.7.5.2 --- Problem Set Two --- p.105Chapter 4.7.5.3 --- Problem Set Three --- p.107Chapter 4.7.5.4 --- Problem Set Four --- p.107Chapter 4.8 --- Conclusions --- p.109Chapter 5 --- Dynamic Programming and Lower Bounds --- p.110Chapter 5.1 --- Dynamic Programming (DP) --- p.110Chapter 5.1.1 --- Introduction --- p.110Chapter 5.1.2 --- Modified Dynamic Programming algorithm --- p.112Chapter 5.1.3 --- Comparison between optimal solution and heuristics --- p.120Chapter 5.1.4 --- Comparison between optimal solution and the GA --- p.123Chapter 5.2 --- Lower Bounds --- p.123Chapter 5.2.1 --- Introduction --- p.123Chapter 5.2.2 --- The U-line Balancing Problem and The Bin Packing Problem --- p.127Chapter 5.2.3 --- Martello and Toth's lower bounds for The BPP --- p.128Chapter 5.2.3.1 --- Bound L1 --- p.128Chapter 5.2.3.2 --- Bound L2 --- p.128Chapter 5.2.3.3 --- Dominances and reductions --- p.129Chapter 5.2.3.3.1 --- Dominance criterion --- p.129Chapter 5.2.3.3.2 --- Reduction procedure --- p.130Chapter 5.2.3.4 --- Lower Bound LR --- p.131Chapter 5.2.4 --- Chen and Srivastava's lower bounds for The BPP --- p.131Chapter 5.2.4.1 --- A unified lower bound --- p.132Chapter 5.2.4.2 --- Improving Lm --- p.133Chapter 5.2.4.3 --- "Computing a lower bound on N(1/4,1]" --- p.134Chapter 5.2.5 --- Lower bounds for The U-line Balancing Problem --- p.137Chapter 5.2.5.1 --- Lower bounds on number of stations required --- p.137Chapter 5.2.5.2 --- Lower bounds on total cost --- p.139Chapter 5.2.6 --- Computational results --- p.140Chapter 5.2.6.1 --- Results for different Problem Sets --- p.140Chapter 5.2.6.2 --- Comparison between lower bounds and optimal solutions --- p.143Chapter 5.2.6.3 --- Comparison between lower bounds and heuristics --- p.145Chapter 5.2.6.4 --- Comparison between lower bounds and GA --- p.147Chapter 5.3 --- Conclusions --- p.149Chapter 6 --- Conclusions --- p.150Chapter 6.1 --- Summary of achievements --- p.150Chapter 6.2 --- Future works --- p.15