This dissertation addresses the "multi-machine carryover sequence
dependent group-scheduling problem with anticipatory setups," which arises in
the printed circuit board (PCB) manufacturing. Typically, in PCB manufacturing
different board types requiring similar components are grouped together to
reduce setup times and increase throughput. The challenge is to determine the
sequence of board groups as well as the sequence of individual board types within
each group. The two separate objectives considered are minimizing the makespan
and minimizing the mean flow time.
In order to quickly solve the problem with each of the two objectives, highly
effective metasearch heuristic algorithms based on the concept known as tabu
search are developed. Advanced features of tabu search, such as the long-term
memory function in order to intensify/diversify the search and variable tabu-list
sizes, are utilized in the proposed heuristics.
In the absence of knowing the actual optimal solutions, another important
challenge is to assess the quality of the solutions identified by the proposed metaheuristics.
For that purpose, methods that identify strong lower bounds both
on the optimal makespan and the optimal mean flow time are proposed. The
quality of a heuristic solution is then quantified as its percentage deviation from
the lower bound. Based on the minimum possible setup times, this dissertation
develops a lower bounding procedure, called procedure Minsetup, that is capable
of identifying tight lower bounds.
Even tighter lower bounds are identified using a mathematical programming
decomposition approach. Novel mathematical programming formulations
are developed and a branch-and-price (B&P) algorithm is proposed and implemented.
A Dantzig-Wolfe reformulation of the problem that enables applying
a column generation algorithm to solve the linear programming relaxation of
the master problem is presented. Single-machine subproblems are designed to
identify new columns if and when necessary. To enhance the efficiency of the
algorithm, approximation algorithms are developed to solve the subproblems. Effective
branching rules partition the solution space of the problem at a node where
the solution is fractional. In order to alleviate the slow convergence of the column
generation process at each node, a stabilizing technique is developed. Finally, several
implementation issues such as constructing a feasible initial master problem,
column management, and search strategy, are addressed.
The results of a carefully designed computational experiment for both
low-mix high-volume and high-mix low-volume production environments confirm
the high performance of tabu search algorithms in identifying extremely good
quality solutions with respect to the proposed lower bounds. / Graduation date: 2006
| Identifer | oai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/28759 |
| Date | 22 September 2005 |
| Creators | Geloğullari, Cumhur Alper |
| Contributors | Logendran, Rasaratnam |
| Source Sets | Oregon State University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis/Dissertation |
Page generated in 0.0165 seconds