| year | 2002 |
|---|---|
| author | Yangja Jang |
| Keyword | scheduling, flexible job shop, multi-level job structure, genetic algorithm, large step optimization |
| Abstract | It is evident that there are disparities between scheduling theory and shop floor requirements. One of these is manufacturing flexibility, which supports various manufacturing alternatives to produce a product, and another is jobs hierarchy, which describes the gozinto relationships between jobs. In this paper, we deal with the flexible job shop scheduling problem in the processing of multi-level jobs. A flexible job shop can be defined as a general job shop consisting of workcenters composed of identical parallel machines. This situation adds the machine selection problem to the standard job shop scheduling which only sequences operations at each machine. Owing to the multi-level job structure, we also control the coordination and pacing of low level components. Three mathematical models respecting different manufacturing environments have been proposed. This paper has proposed a new gene design, used in the genetic algorithm, to represent machine assignment, operation sequences, and the relative level of the operation to the final operation. The relative operation level is the control parameter which synchronizes the completion timing of the components belonging to the same branch in the job hierarchy. We compare the effectiveness of the genetic algorithm utilizing relative operation levels with that of several dispatching rules in terms of total tardiness, sum of total tardiness and total earliness, and makespan. The genetic algorithm reveals outstanding performance in the solution performance of forty modified standard job shop problems. For the small sized problems, we compare the best solution of MIP optimizer and the best solution of genetic algorithm and it shows the good performance of genetic algorithm. The genetic algorithm shows good promise as a scheduling tool in a flexible job shop with multi-level job structures. In order to revise the fixed relative level which solutions are confined to, we apply large step transition in the firs step and genetic algorithm in the second step. We call this procedure as large step optimization. We compare the genetic algorithm and large step optimization in terms of total tardiness and makespan for about forty modified standard job-shop problem instances. Large step optimization decreases 17% in the total tardiness and 15% in the makespan of genetic algorithm respectively. The large step transition suggested in this paper seems to lead the solution of genetic algorithm to the improved solution region. Finally, we propose mathematical model which assigns the due date of newly entered customer orders and propose binary search process which seeks the possible due date. |
| c | PhD |
Download :