Scheduling of manufacturing systems with reentrant work flows and sequence dependent setup times

Abstract

The purpose of this thesis is to develop effective scheduling methodologies for real-life shop scheduling problems which have several complicated operating characteristics. Effective control of material movement through manufacturing facilities becomes a very important issue in today``s highly competitive environment. In the first part of the thesis, we consider two kinds of scheduling problems of a flow line with a set of jobs given. The flow line consists of two machines where only one of them has separable, external, and sequence-dependent setup times. A most unusual aspect of the problems is that the setup times required for a job in one of the two machines depend not on the immediately preceding job but on the job which is n steps prior to it. The problems are solved by a dynamic programming with the objective of the minimum makespan. An optimal schedule is found utilizing the sequence dominance condition. Since the computational requirements of the dynamic programming are impracticably demanding for large-sized problems, a genetic algorithm is developed whose performance is examined through a comparative study. The second part addresses a shop scheduling problem where a set of n jobs needs to be scheduled on two machines for the side frame press shop in a truck manufacturing company. In the problem, the first machine has sequence-dependent setup times and the length of setup times required for a job depends on the job which is two steps prior to it. Moreover, the problem is complicated by the presence of reentrant work flows. Redefining the job elements, the problem is formulated into a general two machine flow shop problem which can be solved by a dynamic programming with the objective of the minimum makespan. An optimal schedule is found utilizing the sequence dominance conditions and the decision-delay scheme. Due to the impracticably demanding computational requirements of the dynamic programming for large-sized problems, a genetic algorithm is deve...