Joint job/tool scheduling in a flexible manufacturing cell with no on-board tool magazine

This paper deals with the joint part/toolscheduling problem in aflexiblemanufacturingcell consisting of two machines. Each job requires a set of tools for the execution of a sequence of operations. The tools are stored in a shared toolmagazine and are moved throughout the cell by means of atool handling system; a conflict may arise when the two machines, which have no on-boardmagazine, simultaneously require the same tool. We want to schedule each single operation to optimize a performance measure such as makespan or maximum lateness. To this aim, the jobs must be allocated and sequenced on the machines, and the single operations must be scheduled to avoid conflicts on tools. A relevant fact for makespan minimization is that, given ajob sequence for the two machines, the toolscheduling problem can be easily solved at optimality as a two-jobsjob shop problem. This suggests a problem decomposition strategy; tabu search may be adopted to search over the space of job sequences, using the two-job routine to compute the corresponding optimal makespan. Alternatively, toolscheduling may be tackled by simple priority rules; this is necessary for the maximum lateness objective, for which polynomial complexity algorithms are not known. We illustrate and compare different decompositions for our problem, to assess the best compromise between computational effort and solution quality.