# Presentation: 531752

## Combinatorial Optimization Treatment of the Unary NP-Complete Disassembly Line Balancing Problem

**Combinatorial Optimization Treatment of the Unary NP-Complete Disassembly Line Balancing Problem**
**Ph.D. Dissertation Defense**
**by**
**Seamus M. McGovern**
- Dissertation Advisor, Dr. Surendra M. Gupta
**Committee Member, Dr. Ronald F. Perry**
**Committee Member, Dr. Sagar V. Kamarthi**
** ****Committee Member, Dr. N. Elif Kongar**
***Laboratory for Responsible Manufacturing***
***Department of Mechanical and Industrial Engineering***
***Northeastern University***
***Boston, MA 02115***
**October 21,  2005**

## Outline

- Literature review, introduction to disassembly
- Disassembly Line Balancing Problem model
- Complexity theory and proof (NP-complete, unary NP-complete and NP-hard)
- Graphical representation and experimental instances
- Combinatorial optimization searches and analytical methodology

## Outline (cont.)

- Summaries, asymptotic bound calculations and numerical results:
- Exhaustive search
- Genetic algorithm
- Ant colony optimization
- Greedy algorithm
- Greedy/hill climbing hybrid
- Greedy/2-opt hybrid
- Uninformed search
- Solution methodology comparison
- Conclusions

## Literature Review

- Environmentally conscious manufacturing and product recovery
- Gualtieri (2005), Toffel (2002), Sodhi and Reimer (2001), Schultmann and Rentz (2001), Bader (2004), Kotera and Sato (1997)
- Assembly line balancing and manufacturing systems
- Elsayed and Boucher (1994), Pinedo (2002), Gutjahr and Nemhauser (1964), Erel and Gokcen (1964), Suresh *et al*. (1996), Silverman and Carter (2003), Lapierre *et al*. (2004), Hackman *et al*. (1989), Ponnambalam *et al*. (1999), Thilakawardana *et al*. (2003), Hong and Cho (1997), McMullen and Frazier (1998), Lapierre and Ruiz (2004), Tiacci *et al*. (2003), Bautista and Pereira (2002), McMullen and Tarasewich (2003), Moore *et al*. (1996)

## Literature Review (cont.)

- Disassembly and remanufacturing
- Lambert (1999, 2002, 2003), Lee *et al*. (2001), Gupta and Taleb (1994), Tang *et al*. (2001), Moore *et al*. (2001), Tiwari *et al*. (2001), Kongar and Gupta (2002), Das and Naik (2002), Güngör and Gupta (1997, 1998, 1999, 2001, 2002), O’Shea *et al*. (1999), Torres *et al*. (2004), Duta *et al*. (2002), Veerakamolmal and Gupta (1998, 1999), Lambert and Gupta (2002), Franke *et al*. (2005), Kekre *et al*. (2003)
- Optimization and algorithms
- Tovey (2002), Rosen (1999), Lambert and Gupta (2005), Cormen *et al*. (2001), Miller and Freund (1985), Cook (1971), Karp (1972), Papadimitriou and Steiglitz (1998), Garey and Johnson (1979), Holland (1975), Koza (1992), Dorigo *et al*. (1996, 1999), Hopper and Turton (2000), Osman and Laporte (1996, 2004), McGovern *et al*. (2003), McGovern and Gupta (2004)

## Introduction

- Manufacturers recycling and remanufacturing due to:
- Implementation of extended manufacturer responsibility
- New more rigid environmental legislation
- Increased public awareness
- Economic attractiveness of reusing products and subassemblies or parts
- Recycling: a process performed to retrieve the material content of used and non-functioning products
- Remanufacturing: an industrial process where worn-out products are restored to like-new conditions

## Introduction (cont.)

- The first step is disassembly, which has unique challenges
- Inventory problems due to the disparity between the demands for parts and the disassembly yield
- As opposed to the normal "convergent" flow in regular assembly environment, in disassembly the flow process is "divergent" (a single product is broken down into many subassemblies and parts)
- High degree of uncertainty in the structure of returned products
- High degree of uncertainty in the quality of returned products
- Parts may cause pollution or may be hazardous
- Disassembly line balancing requires minimizing the resources for disassembly and maximizing the automation of the process and the quality of the parts or materials recovered

## DLBP Description 

- Seek to fulfill five goals:
- minimize the number of workstations and hence, the total idle time
- ensure the idle times at each workstation are similar
- remove hazardous components early in the disassembly sequence
- remove high-demand components before low-demand components
- minimize the number of direction changes required for disassembly
- The result is an integer, multi-criteria decision making problem with an exponential search space
- The solution consists of a sequence of work elements; i.e., in the eight-tuple 5, 2, 8, 1, 4, 7, 6, 3 subassembly number 5 would be removed first, followed by 2, then 8, etc.

## Balancing Definition

***Definition 1***	A disassembly line is optimally *balanced* when the fewest possible number of workstations is needed and the variation in idle times between all workstations is minimized.  This is mathematically described by
- 	Minimize [max (*ST**x*)  min (*ST**y*)] * x*, *y*  {1, 2,..., *NWS*}
- 	and concurrently
- 	Minimize *NWS.**	***

## DLBP Formulation

## DLBP Formulation (cont.)

***Theorem 1***	Let *PRT**k* be the part removal time for the *k*th of *n* parts where *CT* is the maximum amount of time available to complete all tasks assigned to each workstation. Then for the most efficient distribution of tasks, the minimum number of workstations, *NWS**** satisfies
***Proof*****:**		If the above inequality is not satisfied, then there must be at least one workstation completing tasks requiring more than *CT* of time, which is a contradiction. *	***

## DLBP Formulation (cont.)

## DLBP Formulation (cont.)

## DLBP Formulation (cont.)

- where

- where

- where

## Complexity

- “*Lord, grant me the **serenity to accept the things I cannot change, courage to change the things I can, and **wisdom to know the difference*.” (The Serenity Prayer, Anonymous)

## Complexity (cont.)

- Some common complexity classes:
*P* or “polynomial” (i.e., easy to find)
*NP* or “nondeterministic polynomial time” (i.e., easy to check; solved “yes” or “no” by polynomial time nondeterministic algorithm)
*NP-hard* (optimization or decision problem, whether a member of NP or not, to which an NP-complete problem can be transformed; optimization version)
*NP-complete* (i.e., in NP and any one of the “complete” or equivalent problems can be converted to it – not the reverse, per Cook and Karp; decision only)
*Unary NP-complete* (i.e., NP-complete and thought not to be solvable by a pseudo-polynomial time algorithm)
*Co-NP-complete*, *PSPACE-complete*, etc.
- Million-dollar question: P = NP? (one of the seven *Millenium **Prize Problems*)

## Complexity (cont.)

- The decision version of DLBP is NP-complete in the strong sense
- Shown using the concise style of Garey and Johnson through proof by restriction
- Verification is omitted for brevity;  DLBP is easily seen to be solvable in polynomial time by a nondeterministic algorithm

## Complexity (cont.)

- INSTANCE:	A finite set *P* of tasks, partial order     on *P*, task time *PRT**k***Z****+**, hazardous part binary value *h**k*{0, 1}, part demand *d**k***N**, and part removal direction *r**k***Z** for each *k**P*, workstation capacity *CT***Z****+**, number *NWS***Z****+** of workstations, difference between largest and smallest idle time *V*N, hazard measure *H***N**, demand measure *D***N**, and direction change measure *R***N**.

## Complexity (cont.)

- QUESTION:	Is there a partition of *P* into disjoint sets *P**A*, *P**B*,..., *P**NWS* such that the sum of the sizes of the tasks in each *P**X* is *CT* or less, the difference between largest and smallest idle times is *V* or less, the sum of the hazardous part binary values multiplied by their sequence position is *H* or less, the sum of the demanded part values multiplied by their sequence position is *D* or less, the sum of the number of part removal direction changes is *R* or less, and it obeys the precedence constraints?

## Complexity (cont.)

- MULTIPROCESSOR SCHEDULING
- INSTANCE:	A finite set *A* of tasks, a length *l*(*a*)******** for each *a**A*, a number *m********* of processors, and a deadline *B*********.
- QUESTION:	Is there a partition *A* = *A*1*A*2... *A*m of *A* into *m* disjoint sets such that

## Complexity (cont.)

***Theorem 2******	***The decision version of DLBP is unary NP-complete.
***Proof***:		DLBPNP.															Restrict to MULTIPROCESSOR SCHEDULING by allowing only instances in which *V* = *CT*,    is empty, and *h**x* = *h**y*, *d**x* = *d**y*, *r**x* = *r**y*  *x*, *y*  *P*.

## Complexity (cont.)

- Decision version of DLBP is NP-complete
- Decision version of DLBP is NP-complete in the strong sense
- Optimization version of DLBP is NP-hard

## Graphical Representation

*Directed edges* (*arcs*) continue to be depicted as solid lines terminated with arrows; arrow’s direction points towards subsequent disassembly tasks; i.e., leave predecessor parts
- Broken lines to express OR relations by connecting them to each other; i.e., remove (1 AND 2) OR (2 AND 3) prior to 4

## Experimental Instances

- Since DLBP is a recent problem, very few problem instances exist
- Four developed here:
- the personal computer problem instance,
- the 10-part problem instance,
- the cellular telephone problem instance, and
- a variable-size known-solution benchmark set of instances
- Typical auto assembly plant has *CT* = 60 seconds; small aircraft manufacturer provides 31⁄2 hours of cycle time
- Number of components can run into the thousands; even an efficient contemporary auto design (e.g., 2005 Mustang) consists of 4000+ parts; 20 hours to build

## Experimental Instances (cont.)

- Personal computer background:
- More than 20-million new personal computers purchased in U.S. each year
- 10,000 televisions and personal computers taken out of service each day
- Typical computer contains 3 to 8 pounds of lead
- Cost of properly disposing of a PC estimated $30
- Monitor CRTs account for 40% of all lead in U.S. waste stream
- EPA able to fine $15,000 for every piece of equipment that ends up in a landfill and $25,000-a-day until the machines are cleaned up
- Expectation of 315-million computers obsolete in 2004

## Experimental Instances (cont.)

- Personal computer instance:
- Based on work of Güngör and Gupta
- Objective is to completely disassemble a PC consisting of 8 subassemblies on a paced disassembly line with *CT* = 40
- OR relationship in product; e.g., remove part (2 OR 3) prior to part 6
- Modified from original
- Search space is 8! or 40,320 (due to precedence constraints, there are only 16 feasible solutions)

## Experimental Instances (cont.)

## Experimental Instances (cont.)

- 10-part instance:
- Based on work of Kongar and Gupta
- Objective is to completely disassemble a product consisting of 10 subassemblies on a paced disassembly line with *CT* = 40
- OR relationships in product
- Modified from original by adding DLBP attributes to the disassembly sequencing problem instance
- Search space is 10! or 3,628,800

## Experimental Instances (cont.)

## Experimental Instances (cont.)

- Cellular telephone background:
- Growth of cellular telephone use and rapid changes in technology and features has prompted entry of new models on a regular basis
- 1,000,000 cellular telephones discarded/year
- Typically end up in landfills
- Hazardous parts contain mercury, cadmium, arsenic, zinc, nickel, lead, gallium arsenide and beryllium
- In 2005 companies that refurbished cellular telephones typically paid $2 to $20 per phone for more popular Motorola and Nokia models
- Recyclers paid between $1 and $6 per phone

## Experimental Instances (cont.)

- Cellular telephone instance:
- Developed by Gupta, Evren and McGovern
- 2001 model year Samsung SCH-3500 cell phone
- Objective is to completely disassemble a product consisting of 25 subassemblies on a paced disassembly line with *CT* = 18
- No OR relationships
- Search space is 25! or 1.55  1025

## Experimental Instances (cont.)

## Experimental Instances (cont.)

- Benchmark data sets common for NP-complete problems (*Oliver30* and *RY48P* for TSP, *Nugent15/20/30*, *Elshafei19*, and *Krarup30* for QAP)
- Due to size and design, these data sets have no known optimal answer (solutions compared to best-known solution to-date)
- Since DLBP is a recently defined problem, no appropriate benchmark data sets exist

## Experimental Instances (cont.)

- Data set proposed to always provide known solution
- Done using prime part removal times
- Chosen instances made up of parts with times of 3, 5, 7, 11 and *CT* = 26
- Optimal balance for would consist of permutations of 3, 5, 7, 11 at each workstation and idle times of 0
- Known optimal results: *F**** = 0, *H**** = 1, *D**** = 2, *R**** = 1

## Experimental Instances (cont.)

## Experimental Instances (cont.)

- Equal times and no precedence constraints results in multiple optimum extreme points
- To quantify size of optimal solution set, count sample points using generalized multiplication rule covering *n* operations (probability theory)
- For example, with *n* = 12 and |*PRT*| = 4, size of set of optimally balanced solutions when using DLBP *A Priori* data calculated as |*F**| = (12  9  6  3)  (8  6  4  2)  (4  3  2  1) = 17,915,904

## Experimental Instances (cont.)

## Experimental Instances (cont.)

## Experimental Instances (cont.)

- When all objectives considered, there still exist multiple optimal solutions
- Using example *n* = 12 and |*PRT*| = 4, known that size of the set of solutions optimal in *F, H, D, *and* R* calculated as: |*F*** H*** D*** R**| = (1  1  6  3)  (4  3  2  1)  (4  3  2  1) = 10,368

## Experimental Instances (cont.)

## Experimental Instances (cont.)

## Experimental Instances (cont.)

## Experimental Instances (cont.)

## Comb. Opt. Searches

*“**Complexity theory is usually just an excuse for laziness.  Give me a problem: I’ll solve it.” *(Dantzig, 1979)

## Comb. Opt. Searches (cont.)

- 7 techniques selected for study and comparison
- 2 probabilistic distributed intelligent agent metaheuristics (GA and ACO)
- 2 basic deterministic searches (greedy and H-K)
- 2 hybrid techniques (greedyAEHC and greedy/2-opt)
- exhaustive search; as a benchmark

## Comb. Opt. Searches (cont.)

- For consistency in SW architecture, data structures and time complexity, all software was expressly designed; no off-the-shelf programs were used
- Any sections of code that could be used by multiple programs were reused
- Written in ANSI C++ (specifically Visual C*++*)
- Run on 1.6GHz PMx86-family workstation 512MB RAM
- During data collection, no other SW running or open

## Analytical Methodology

*“...**very little has been established about the performance of (heuristics).  Developing the mathematical methodology for explaining and predicting the performance of...heuristics is one of the most important challenges facing the fields of optimization and algorithms today.” *(Papadimitriou and Steiglitz, 1998)

## Graphical Analysis Tools

- Time complexities provided in *asymptotic notation* (*big-Oh*, *big-Omega* and *big-Theta*)
- Tables are used to observe the solution of any single instance
- Charts provide a graphical comparison of known best- and worst-case results with calculated; charts include:
- number of workstations with optimal,
- balance measure with optimal,
- normalized balance measure with optimal and nominal,
- hazard measure with optimal and nominal,
- demand measure with optimal and nominal,
- direction measure with optimal and nominal,
- average-case time complexity with overlaid 1st-, 2nd-, or 3rd-order polynomial trend line (linear or polynomial regression models),
- average-case time complexity with third-order and exhaustive growth curves, and
- average-case time complexity with a second-order curve

## MCDM Considerations

- Determining all alternative optima is enabled by;
- given multiple optimum extreme points in *F*, early removal of hazardous parts is considered,
- given multiple optimum extreme points in *F *and* H*, early removal of high-demand parts is considered next,
- given multiple optimum extreme points in *F*, *H*, and* D*, adjacent removal of parts with equivalent part removal directions is considered
- MCDM technique borrows from preemptive (lexicographic) goal programming (GP)
- GP conceptualizes objectives as goals and assigns priorities to the achievement of goals
- In preemptive GP, goals are grouped according to priorities; goals at highest priority level are considered infinitely more important than goals at second priority level, and so forth

## Efficacy Analysis

- Primary mathematical tool developed for quantitative analysis is the *efficacy index*
- Ratio of the difference between a calculated measure and its worst-case measure to the measure’s sample range (from area of statistical quality control) and expressed as a percentage

## Efficacy Analysis (cont.)

- Additional quantitative tool from statistics: Simple linear regression and correlation (using sample coefficient of determination), and polynomial regression and its associated coefficient of multiple determination are used to quantify the accuracy of the curves and to provide the regression equation

## Exhaustive Algorithm

- Exhaustive search algorithm developed to:
- confirm exponential time growth of exhaustive search,
- provide time complexity benchmark for subsequent studies, and
- determine optimal solutions for any data set up to a given size
- Built around a recursive function that generated all permutations of a sequence of *n* numbers
- Purpose of this exhaustive algorithm is to find every subset of the data set (every permutation) and from all those subsets, find the solution set that best satisfies the multi-criteria performance requirements by checking against all other permutations
- Worst-case time complexity of recursive depth-first search routine (big-Oh of **(*n*!)) is equal to best case (big-Omega of (*n*!)),  tight time complexity asymptotic bound exists with big-Theta of (*n*!)

## Exhaustive Results; PC

- PC instance:
- 4 workstations, *F** = 33, *H** = 7, *D** = 19025 and *R**** = 6; averaged less than 1/100th of a second

## Exhaustive Results; 10

- 10-part instance:
*NWS** = 5, *F** = 211, *H** = 4, *D** = 9730 and *R**** = 7; averaged 0.03 seconds

## Exhaustive Results; A Priori

*A Priori* instance with *n* = 12:
*NWS**** = 3, *F**** = 0, *H**** = 1, *D**** = 2 and *R**** = 1; time to complete search averaged 24.61 minutes
- Note this is only one of 10,368 optimum extreme points at *n* = 12 (very first optimal solution visited by Exhaustive Search)

## Exhaustive Results; cell

- Cellular telephone instance:
- Using actual growth proportionate to 1.199(*n*!) gives an *n* = 16 runtime of 2.04 years and a cellular telephone instance runtime of 15,150,310,402 centuries; universe is generally accepted to be 137,000,000 centuries old

## Time Complexity

## Genetic Algorithm

- Random/hot start feasible initial population, calculate fitness
- Randomly select *R**x**N* parents
- Create *R**x**N* children using PPX
- Randomly mutate *R**m*  100 % of children
- Remove *R**x**N* duplicates and least fit parents
- Add children to population
- Calculate fitness of new generation
- Repeat for multiple generations

## GA Complexity

- Time complexity is a function of number of generations, population size *N* and chromosome size *n*
*T*(*n*)  *n**N*(number of generations)
- Population and number of generations considered to stay constant with instance size,  best case:
- (*n*)
- Worst case requires no more processing time than *n**N*(number of generations),  worst case:
**(*n*)
- Tight time complexity bound:
- (*n*)

## GA Numerical Results; PC

- PC instance:
- 4 workstations, *F** = 33, *H** = 7, *D** = 19025 and *R**** = 6; averaged 3.30 seconds per run over five runs

## GA Numerical Results; 10

- 10-part instance:
*NWS** = 5, *F**** = 211, *H* = 4.80 (best *H** = 4 and worst *H* = 5), *D* = 9054.00 (best *D* = 8885 and worst *D**= 9730) and *R* = 7.80 (best *R**** = 7 and worst *R* = 8); 3.16 seconds averaged over five runs

## GA Numerical Results; cell

- Cellular telephone instance:
*NWS* = 9, *F* = 81, *H* = 78.40 (best *H* = 78 and worst *H* = 79), *D* = 916.20 (best *D* = 914 and worst *D* = 920) and *R* = 10.60 (best *R* = 10 and worst *R* = 12); 2.26 seconds on average

## Time Complexity (99.17%)

## ACO Metaheuristic

- Each ant’s possible subsequent steps (i.e., from any node *p* to a node *q*, giving an edge *pq*) are evaluated for desirability and each is assigned a proportionate probability
- Based on these probabilities, the next step in the tour is randomly selected (using a weighted probability) for each ant
- After completing an entire tour, each feasible ant is given the equivalent of additional pheromone (proportionate to how desirable the tour is and referred to as “trail”), which is added to each step that ant has taken
- All paths are decreased in pheromone strength according to a measure of evaporation
- This process is repeated for a maximum number of cycles or until stagnation behavior (i.e., where all ants make the same tour)

## ACO probability and trail

## ACO Complexity

- Best case (when *m* = 1):
*T*(*n*)  2(*n*  1) + 2(*n*  2) +...+ 2(2)
*T*(*n*)  2( *n*(*n*  1)  (1 + 2 +...+ (*n*  2)) )
*T*(*n*)  2*n*(*n*  2)  2
*T*(*n*)  2*n*(*n*  2)  (*n*  2)((*n*  2) + 1)
*T*(*n*)  *n*2  *n * 2

- Worst case (when *m* = *n*):
*T*(*n*)  *m*(*n*2  *n * 2)
*T*(*n*)  *n*3  *n*2  2*n*

## ACO Numerical Results; PC

- PC instance:
- 4 workstations, *F** = 33, *H** = 7, *D** = 19025 and *R**** = 6; averaged 0.65 seconds per run over five runs

## ACO Numerical Results; 10

- 10-part instance:
*NWS** = 5, *F**** = 211, *H* = 4.40 (best *H** = 4 and worst *H* = 5), *D* = 10736.00 (best *D* = 10090 and worst *D* = 11635) and *R* = 7.00 (best *R* = 6 and worst *R**nom* = 8); 1.14 seconds averaged over five runs

## ACO Numerical Results; cell

- Cellular telephone instance:
*NWS* = 9, *F* = 9.80 (best *F* = 9 and worst *F* = 13), *H* = 86.40 (best *H* = 82 and worst *H* = 90), *D* = 921.80 (best *D* = 868 and worst *D* = 952) and *R* = 11.60 (best *R* = 11 and worst *R* = 12); 7.38 seconds on average

## Time Complexity (100.0%)

## DLBP Greedy

- Each part in sorted list is examined from first to last
- If not previously put into solution, part is put into current workstation if idle time remains and that position will not violate any precedence constraints
- If none can accommodate it due to precedence constraints, part is maintained on the sorted list and next part (not yet selected) on the list is considered
- If all parts have been examined for insertion into the current workstation, a new workstation is created and the process is repeated
- As is the norm with greedy, run once to solution

## DLBP Greedy (cont.)

- While being very fast and efficient, the algorithm is not always able to minimize the number of workstations
- In addition, no capability to balance the workstations; in fact, the FFD structure lends itself to filling the earlier workstations as much as possible, often to capacity, while later workstations have progressively greater and greater idle times
- Result is extremely poor balance
- This limitation led to the development of AEHC

## Greedy Complexity

- Bubble Sort:

- FFD best case:

- Greedy best case:

- FFD worst case:

- Greedy worst case:

## Greedy Num. Results; PC

- PC instance:
- 4 workstations, *F** = 33, *H** = 7, *D** = 19025 and *R**** = 6; less then 1/100th of a second

## Greedy Num. Results; 10

- 10-part instance:
*NWS** = 5, *F* = 393 (*F**** = 211), *H** = 4, *D* = 10590 (*D**** = 9730) and *R* = 8 (*R**** = 7); less then 1/100th of a second

## Greedy Num. Results; cell

- Cellular telephone instance:
*NWS* = 10, *F* = 199, *H* = 89, *D* = 973 and *R* = 12; less than 1/100th of a second

## Time Complexity (95.71%)

## Greedy/AEHC Hybrid

- Hill-climbing is an iterated improvement algorithm, basically a gradient descent/ascent; makes use of an iterative greedy strategy, which is to move in the direction of increasing value
- A hill-climbing algorithm evaluates the successor states and keeps only the best one
- AEHC designed to consider swapping each task in every workstation with each task in the subsequent workstation
- Only adjacent workstations are compared:
- to enable a rapid search, and
- since deemed unlikely that parts several workstations apart can be swapped and still preserve precedence of tasks in-between

## The DLBP AEHC Heuristic

## Greedy/AEHC Complexity

- With greedy (best):

- With greedy (worst):

- Least number of comparisons:

- Highest number of comparisons:

## Greedy/AEHC Results; PC

- PC instance:
- 4 workstations, *F** = 33, *H** = 7, *D** = 19025 and *R**** = 6; less than 1/100th of a second

## Greedy/AEHC Results; 10

- 10-part instance:
*NWS** = 5, *F* = 369, *H** = 4, *D* = 9840 and *R* = 6 (versus *R**** = 7, though at the expense of sub-optimal balance and demand measures); less than 1/100th of a second

## Greedy/AEHC Results; cell

- Cellular telephone instance:
*NWS* = 10, *F* = 199, *H* = 89, *D* = 973 and *R* = 12; less than 1/100th of a second

## Time Complexity (99.09%)

## Greedy/2-Opt Hybrid

- In *r*-opt, all exchanges of *r* edges are tested until there is no feasible exchange that improves the current solution (*r*-optimal); rapidly increases in *r*; *r* = 2 and *r* = 3 are most commonly used; greedy solution is generally considered the best starting point
- In 2-Opt, two tours are neighbors if one can be obtained from the other by deleting two edges, reversing one of the resulting two paths, and reconnecting
- In DLBP 2-Opt, neighbors of the tour are pair-wise part exchanges within the current solution sequence
- With *n* = 4 and an original solution sequence of 1, 2, 3, 4, the six resulting pair-wise exchanges are 2, 1, 3, 4, 3, 2, 1, 4, 4, 2, 3, 1, 1, 3, 2, 4, 1, 4, 3, 2 and 1, 2, 4, 3
- Exhaustive search visits all *n*! tours (24 in this case)

## 2-Opt

## DLBP 2-Opt

## Greedy/2-Opt Complexity

- With greedy (best):

- With greedy (worst):

## Greedy/2-Opt Results; PC

- PC instance:
- 4 workstations, *F** = 33, *H** = 7, *D** = 19025 and *R**** = 6; less than 1/100th of a second

## Greedy/2-Opt Results; 10

- 10-part instance:
*NWS** = 5, *F** = 211, *H** = 4, *D** = 9730 and *R**** = 7; less than 1/100th of a second

## Greedy/2-Opt Results; cell

- Cellular telephone instance:
*NWS* = 10, *F* = 93, *H* = 87, *D* = 943 and *R* = 10; 0.02 seconds on average

## Time Complexity (91.95%)

## H-K Motivation

- In many search applications (anti-submarine warfare, search and rescue, air cavalry), exhaustive search not possible due to time or sensor limitations
- Becomes necessary to sample the search space and assume that the visited optimal point is either the global optimal point or is reasonably near
- H-K search technique works by sampling the exhaustive solution set (similar to these hunter-killer, or H-K, applied search methods)
- Performed using a search pattern that skips solutions to significantly minimize search space

## H-K Metaheuristic

## H-K Metaheuristic (cont.)

## H-K Metaheuristic (cont.)

- Once solution is generated, the space can be further searched with additional application of the H-K metaheuristic (using a different starting point) or the best-to-date solution can be further refined by performing subsequent local searches (such as 2-Opt or smaller, localized H-K searches; i.e., using the solution as the starting point, decreasing the skip size, and limiting the range of each element in the subsequent search)
- H-K can be run:
- once
- multiple times on subsequent solutions
- multiple times from the same starting point using different skip measure (potentially as a multiprocessor application)
- multiple times from a different starting point using the same skip measure (potentially as a multiprocessor application)
- followed up with H-K or another, differing local search on the best or several of the best sub-optimal solutions generated

## DLBP H-K

- If all possible parts for a given solution position fail checks:
- remainder of positions are not further inspected
- procedure falls back to the previously successful solution addition
- increments it
- continues
- These processes are repeated until all allowed items have been visited in first solution position (and by default, due to the nested nature of the search, all subsequent solution positions)
- For example, with *n* = 4, ** = 2 and forward-only, instead of considering 4! = 24 possible permutations, only 5 are visited:
*PS**k* = 1, 2, 3, 4
*PS**k* = 1, 4, 2, 3
*PS**k* = 3, 1, 2, 4
*PS**k* = 3, 1, 4, 2
*PS**k* = 3, 4, 1, 2

## DLBP H-K (cont.)

- For *n* = 5, ** = 2 and fwd-only; 5! = 120, H-K considers 16:
*PS**k* = 1, 2, 3, 4, 5
*PS**k* = 1, 2, 5, 3, 4
*PS**k* = 1, 4, 2, 3, 5
*PS**k* = 1, 4, 5, 2, 3
*PS**k* = 1, 4, 5, 2, 3
*PS**k* = 3, 1, 2, 4, 5
*PS**k* = 3, 1, 4, 2, 5
*PS**k* = 3, 1, 4, 5, 2
*PS**k* = 3, 4, 1, 2, 5
*PS**k* = 3, 4, 1, 5, 2
*PS**k* = 3, 4, 5, 1, 2
*PS**k* = 5, 1, 2, 3, 4
*PS**k* = 5, 1, 4, 2, 3
*PS**k* = 5, 3, 1, 2, 4
*PS**k* = 5, 3, 1, 4, 2
*PS**k* = 5, 3, 4, 1, 2

## H-K Results, Varying 

- H-K is purely deterministic and performs no preprocessing,  order data presented expected to affect solutions
- Data forward and reverse
- All cases have *n* = 12, consideration of all **s; i.e., ** = {1,..., *n*}, and using all smaller skip sizes
- Instance size is largest multiple of |*PRT*| that could be repeatedly evaluated by exhaustive search in a reasonable amount of time (*n* = 12 just over 20 min.; *n* = 16 calculated to take over 2 yrs)
- H-K appears to grow about factorially to inverse of **, average time complexity (*b**b*) in **, where *b* = 1/** so small increase in ** will yield a significant speed-up

## Time Complexity Detail

## Workstation Calculation

## Balance Calculation Detail

## Normalized Balance Calc.

## Hazard Calculation

## Demand Calculation

## Direction Calculation

## H-K Numerical Results; PC

- PC instance:
- 3  **  7; forward only
- 4 workstations, *F** = 33, *H** = 7, *D* = 19265 (*D** = 19025) and *R**** = 6; less than 1/100th of a second

## H-K Numerical Results; 10

- 10-part instance:
- 3  **  9; forward only
*NWS** = 5, *F** = 211, *H** = 4, *D* = 10810 (*D** = 9730) and *R* = 6 (*R**** = 7; better than optimal, though at the expense of demand); less than 1/100th of a second

## H-K Numerical Results; cell

- Cellular telephone instance:
- 15  **  24; forward only
*NWS* = 11, *F* = 399, *H* = 82, *D* = 940 and *R* = 10; 0.01 seconds on average

## Time Complexity (99.74%)

## Comparative Analysis

## Workstation Calculation

## Balance Calculation Detail

## Normalized Balance Calc.

## Hazard Calculation

## Demand Calculation

## Direction Calculation

## Time Complexity

## Time Complexity Detail

## Asymptotic Notation

## Efficacy Summary

## Research Summary

- DLBP qualitatively introduced, mathematically defined, proven unary NP-complete
- Seven combinatorial optimization approaches to DLBP presented with four problem instances
- Although near-optimum, DLBP versions of ACO and GA metaheuristics, H-K heuristic, greedy algorithm, greedy/hill-climbing and greedy/2-opt hybrids quickly found feasible, near-optimal solutions in DLBP’s large search space
- Methods well suited to multi-criteria decision making problem format as well as for the solution of problems with nonlinear objectives

## Research Summary (cont.)

- Suited to integer problems; requirement of disassembly problems that generally do not lend themselves to easy solution by traditional optimum mathematical programming techniques
- Consistent generation of near-optimal solutions, ability to preserve precedence, superior speed, and practicality due to ease of implementation
- Dissertation focused on applying a rigorous combinatorial optimization treatment to problem of balancing the disassembly line, including multiple objectives under various restrictions

**Thank You**