Tabu search for resource-constrained scheduling

In this paper, a tabu search algorithm for a resource-constrained scheduling problem (RCSP) that generalizes the job shop scheduling problem is presented. In this scheduling problem machines are capable of processing several operations simultaneously, and operations may require multiple resources for processing with different processing times on each resource. Operations may furthermore have several alternative resource sets by which they can be processed. A sufficiently connected neighborhood is presented from which a priori non-improving neighbors are excluded, which reduces neighborhood sizes substantially. The neighborhood is embedded in a tabu search algorithm that uses intensification around previously found good solutions. the algorithm is tested on two types of instances, viz., multiple capacitated job shop instances and job shop instances with resource sets alternatives, which are derived from well-known job shop instances.