A Job-Scheduling Problem Involving Sequence-Dependent Changeover Costs

Abstract

This paper studies a problem of job scheduling in a production line having various adjustable settings or ‘states’ that can process a variety of jobs. Each job can be processed when the line is in one of the several states at a cost dependent on the state used. One state is sufficient for the processing of each job. In addition, a sequence-dependent changeover cost is also incurred between states. The problem is to determine an optimal sequence of the states of the line, and allocation of jobs to states that minimizes the overall operating cost. An exact implicit enumeration algorithm, which exploits the similarity of this problem with the simple plant location problem, is proposed. Computational experience with the algorithm shows that any reasonable size problem can be solved in comparatively small computational effort.