A Broader View of the Job-Shop Scheduling Problem

Abstract

We define a job-shop scheduling problem with three dynamic decisions: assigning due-dates to exogenously arriving jobs, releasing jobs from a backlog to the shop floor, and sequencing jobs at each of two workstations in the shop. The job-shop is modeled as a multiclass queueing network and the objective is to minimize both the work-in-process (WIP) inventory on the shop floor and the due-date lead time (due-date minus arrival date) of jobs, subject to an upper bound constraint on the proportion of tardy jobs. A general two-step approach to this problem is proposed: (1) release and sequence jobs in order to minimize the WIP inventory subject to completing jobs at a specified rate, and (2) given the policies in (1), set due-dates that will attempt to minimize the due-date lead time, subject to the job tardiness constraint. A simulation study shows that this approach easily outperforms other combinations of traditional due-date setting, job release, and priority sequencing policies for two cases (moderately loaded and heavily loaded) of a particular shop. As a result of the study, three scheduling principles are proposed that can significantly improve the performance of a two-station job-shop; in particular, better due-date performance can be achieved by ignoring due-dates on the shop floor. Although we have only considered a two-station shop, the approach and scheduling principles presented here might also be useful for larger shops.