Year

2002

Degree Name

Doctor of Philosophy

Department

Department of Information Systems

Abstract

The flow-shop problem has been a problem for production management ever since the manufacturing industry began. This problem involves the scheduling of production processes for manufacturing orders (referred to as jobs), where each job requires the same processing sequence and thus the same processing facilities (referred to as machines), although the processing time for a job on a machine may be different from that of a different job. The objective is to find a schedule that can complete all jobs in the shortest possible time under the constraints of machine availability. The fact that more than one job may be chosen to be processed on a machine at any one time has made this problem combinatorial in nature. The most unwanted characteristic of a combinatorial problem is the explosive growth of the solution space and hence the computation time. In mathematical terms, the number of possible schedules for n jobs and m machines is (n!)m.

Early research in this area is mainly based on Johnson's theorem (Johnson, 1954). For flow-shop problems with only two machines or three machines with certain characteristics and an arbitrary number of jobs, Johnson's theorem provides simple procedures for finding an optimal solution. The optimal solution is the sequence of arbitrary number of jobs that will minimise the maximum flow-time (makespan or schedule time). Unfortunately, this theorem does not extend to general three-machine problems or problems involving more than three machines.

The aim of this research is to define a new solution procedure (algorithm) for finding an optimal solution for the three-machine flow-shop problem. In this research, a significant contribution has been made by developing an algorithm that can solve flow-shop scheduling problems beyond two machines. The three-machine flow-shop heuristic algorithm we have developed will always produce an optimal sequence. One characteristic of the algorithm developed in this research is its ability to learn past history to improve on the future search processes. The process of learning from past history reduces the disadvantage of the large computation time associated with most flow-shop scheduling algorithms. In the process of developing the algorithm, we have introduced two important improvements related to the way we estimate the initial distance to the goal at the start of the search and during the search. In with minor modifications the algorithm we have developed can find efficiently multiple optimal solutions when they exist. We envisage that the algorithm developed in this research will contribute significantly to the manufacturing industry, computer industry, digital data communication and transportation industries. The results of research will be presented in five chapters.

In chapter 1 we discuss the basic concepts related to scheduling and we define the special terms used in the field. Then, we discuss the two-machine flow-shop problem and its solution as well as developments to date relating to the three-machine flowshop problem. Finally we consider the development of modern heuristic algorithms for searching, especially the A* algorithm and modifications to A* which make it more efficient.

In chapter 2 we gradually develop our new heuristic algorithm for solving the threemachine problem. The new algorithm is based on the Search and Learning A* algorithm and is developed to ensure that the algorithm is optimal and complete. begin with the development of a heuristic algorithm for the two-machine problem and after introducing an important improvement to that algorithm w e are able to extend the algorithm to use with problems involving three machines.

As is usually the case with algorithms using heuristic functions, we can improve the performance of the algorithm by choosing a high quality heuristic function which underestimates the minimum makespan (is admissible) but is very close to it. In chapter 3 we analyse and compare a set of heuristic functions suitable for use with three-machine problem. We establish the admissibility of the functions and describe conditions which enable us to choose from amongst them a heuristic function which closest to the minimum makespan. Chapter 3 concludes with a statement of the new heuristic algorithm incorporating improvements developed in chapter 2 as well as guidelines for choosing a high quality heuristic function.

In chapter 4 we compare the use of the flow-shop heuristic algorithm developed in chapter 3 with the use of the genetic algorithm described in chapter 1. We discuss other improvements we can apply to the algorithm in terms of memory usage. We modify the flow-shop heuristic algorithm to enable us to find multiple optimal solutions if they exist. We discuss the possibility of applying the algorithm to fourmachine and five-machine flow-shop problems and some possible applications of the algorithm to practical industrial problems.

Chapter 5 presents the conclusions and the findings of this research as well as identifying areas for further related research.

Download

Share

COinS
 

Unless otherwise indicated, the views expressed in this thesis are those of the author and do not necessarily represent the views of the University of Wollongong.