| Optimization of Flowshop Scheduling Problems with Sequence-Dependent Setup Times | |||||||||||||||||||||||||||||||||||
| Funding: |
CONACyT, México (Grant for doctoral studies) U. of Texas - Austin (E. D. Farmer Fellowship) U. of Texas - Austin (David Bruton Fellowship) Texas Higher Education Coordinating Board, ARP/ATP |
||||||||||||||||||||||||||||||||||
| Dates: | 1994 - 1997 | ||||||||||||||||||||||||||||||||||
| People: |
Prof. Jon Bard (U. of Texas) Supervisor
Roger Z. Ríos (U. of Texas)
|
||||||||||||||||||||||||||||||||||
| Summary: |
My Ph.D. dissertation research addressed the flow line
scheduling problem with setup times. In a flow line environment,
there is a set of jobs that must be processed through a set
of machines (e.g., computer assembly lines).
In addition, a setup time, which is dependent on the sequence,
is incurred. The objective is to find a schedule that
minimizes the completion time of all the jobs in the system.
This problem arises in manufacturing environments such as the
pharmaceutical and paint industry. This is a very difficult
problem (classified as NP-hard) in the sense that a
polynomial-time algorithm to find an optimal solution is very
unlikely to exist. During the first part of the research,
I developed two approximation algorithms (heuristics).
The first is based on a technique
that combines greedy heuristics, randomization, and local
search (GRASP). The second is a deterministic procedure that
attempts to exploit the embedded traveling salesman problem
structure. Both heuristics find schedules close to the optimum in
a relatively short amount of time. These algorithms yielded
substantial improvements when compared to the existing work.
The GRASP methodology was awarded first place in the
1st University of Texas Student Research Conference held
in November 1995.
The next stage was to formulate the problem as a mixed integer linear program and to study the polyhedral representation of the set of feasible solutions. Two different models were considered. In this part of the research I developed several valid inequalities for both of these models and established important theoretical properties about their quality. I was able to prove that several of the valid inequalities are indeed "strongest" (facet-defining). I then implemented a branch-and-cut exact optimization scheme based on these polyhedral developments. The branch-and-cut algorithm uses state-of-the-art optimization libraries MINTO and CPLEX. The initial mathematical model was generated with GAMS. Using this code I was able to solve problems that were slightly larger than any previously reported. This work was awarded first place in the 2nd University of Texas Student Research Conference held in October 1996. Two of the most important aspects for an exact optimization technique, such as branch-and-cut or branch-and-bound, to be successful are the ability to generate valid lower bounds (by solving a relaxed subproblem) and the ability to compute upper bounds (by using an approximate algorithm to find feasible solutions). Branch-and-cut methods use linear programming as lower bounding procedures, and in this particular problem it was observed that the LP-bound was still weak. During the research on polyhedral theory I gained significant knowledge about the problem structure that allowed me to devise a better way to find lower bounds. I then implemented a branch-and-bound exact optimization scheme that uses this improved lower bounding scheme, and the approximate algorithm developed during the first stage of the research as an upper bounding procedure. The results were strikingly better, outperforming our previous branch-and-cut method. The BAB solved optimally all 10-job instances, and several 15 and 20 job instances with 2, 4, and 6 machines. When tried over 100-job instances, the BAB finds average relative optimality gaps of about 1-2% for the 2-machine problems (solving 30% of the 2-machine instances). Previous to this work, no instance larger than a 5-machine 7-job had been solved optimally. All of the procedures were written in C and C++.
|
||||||||||||||||||||||||||||||||||
| Publications: |
|
||||||||||||||||||||||||||||||||||