BATCH SEQUENCING

Consider the single machine scheduling problem where there are a number of part types to be processed. A part type is defined as follows: Two parts are of the same part type if the machine does not require a setup in between the processing of these parts. The problem investigated in this paper is to find a sequence of batches of parts (if there are any) where all the requirements for parts are met. A heuristic and an exact algorithm are developed, and computational analysis is performed to measure the performance of the heuristic. The time complexity function of the heuristic is O(n²), and the exact algorithm runs in polynomial time given a fixed upper bound on the number of setups.