|Institution:||University of Otago|
|Keywords:||Scheduling; Job-shop; Limited buffer capacity; Graph representation; Tabu Search|
|Full text PDF:||http://hdl.handle.net/10523/5067|
This dissertation develops an approach to solving a job-shop scheduling problem with a limited buffer capacity. The research problem is derived from solving a container unloading and loading problem at Port Otago. By modelling it as a job-shop problem and designing a graph-based solution for it, the problem can be implemented and solved using a Tabu search framework. The practical problem is a variant of a classic job-shop problem with a limited buffer capacity, input constraints and setup times. The first stage of solving the problem is to model it using a suitable representation. The next stage is to generate an initial solution and convert it into a graph representation. A set of algorithms was designed to propose and implement moves on the graph to improve the cost. Techniques to find valid and improving moves and to calculate new costs were also developed. Then these algorithms and techniques were implemented using a Tabu Search framework which iterates through the neighbourhoods s of the initial solution to find an optimized cost after a certain number of iterations. The results of measurement show that this approach can solve this unloading and loading problem with optimized costs.