Flow-shop Scheduling Framework for Optimizing Resource Utilization under Non-Resumable Unavailability Constraints

Abstract

This study develops a flow-shop scheduling framework for optimizing resource utilization under non-resumable unavailability constraints. These non-resumable interruptions are very common in steel manufacturing industry, chemical processing industry and pharmaceutical industry. Under non-resumable unavailability constraint, if a job is interrupted in mid-processing, then entire work done on the job will be lost and when the machine will be available again then the job has to be started from the scratch. This non resumable interruption can be resolved by two ways either by postponing job’s start time so that it starts processing at the end of unavailable interval on the machine or reschedule jobs so that job complete the processing before the beginning of unavailable interval on the machine. Both corrective strategies will affect the completion time of jobs executing on the current machine and latter indirectly to all downstream machines. In this paper, we have considered n-jobs, 2-machines flow-shop problem having a single non-resumable unavailability constraint on each machine. We have developed an algorithm to obtain an optimal sequence which minimize total elapsed time under non-resumable unavailability constraint. This algorithm is implemented in two steps. At the first step, we find a sequence by applying Modified Johnson’s method to take into consideration the modified completion times that are induced by the non-resumable interruptions. At the second step, we apply Branch-and-Bound method that systematically enumerates the solution space with node pruning to assure global optimality of the sequence. The developed algorithm is illustrated through examples.