Sequence-dependent Setup

In Job Shop Scheduling, sequence-dependent setup occurs when a machine's setup time or cost for a particular job is determined by not only by that job but also by the previous job that the machine is currently setup for. Information on sequence-dependent setup times or costs for N jobs can be stored in a N-by-N matrix with all diagonal entries being zero. Diagonal entries must be zero since they correspond to the condition that the machine is already setup for the next job; hence the setup time and/or cost is zero.

In a job shop, we are usually concerned with completing all of the jobs in the shortest possible time or least possible cost. The time it takes to complete all of the jobs is called Makespan. If set up time or cost does not exist, or is not sequence-dependent, then in a single machine N-job situation, the makespan or total cost is not sequence-dependent. However, when set up times or costs are sequence-dependent, makespan or total cost too becomes variable. The size and complexity of the problem grow rapidly as the number of jobs and machines in the problem increase.