Scheduling problem in a two-machine flow line with the N-step prior-job-dependent set-up times

The purpose of this study is to develop effective scheduling methodologies for the shop scheduling problem of a flow line. The flow line consists of two machines where only the second machine has separable, external, and sequence-dependent set-up times. The length of set-up times required for a job depends not on the immediately preceding job but on the job which is n steps prior to it. The problem is solved by a dynamic programming with the objective of minimizing the make span. 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 and its performance is examined through a comparative study.