A tabu search algorithm with solution space partition and repairing procedure for cyclic robotic cell scheduling problem

Abstract

This paper proposes a tabu search (TS) algorithm to solve an NP-hard cyclic robotic scheduling problem. The objective is to find a cyclic robot schedule that maximises the throughput. We first formulate the problem as a linear program, provided that the robot move sequence is given, and reduce the problem to searching for an optimal robot move sequence. We find that the solution space can be divided into some specific subspaces by the maximal number of works-in-process. Then, we propose a TS algorithm to synchronously perform local searches in each subspace. To speed up our algorithm, dominated subspaces are eliminated by lower and upper bounds of the cycle time during the iterations. In the TS, a constructive heuristic is developed to generate initial solutions for each subspace and a repairing procedure is proposed to maintain the feasibility of the solutions generated in the initialisation stage and the neighbours search process. Computational comparison both on benchmark instances and randomly generated instances indicates that our algorithm is efficient for the cyclic robotic scheduling problem.

Keywords:

• robotic cell
• cyclic scheduling problem
• tabu search
• space partition
• repairing procedure

Acknowledgements

This work was partially supported by the National Natural Science Foundation of China under grant nos. 71101016, 71071129 and 70932005, the China Postdoctoral Science Foundation under grant no. 2011M501407, the Fundamental Research Funds for the Central Universities under grant no. ZYGX2011J110 and the Humanities, Social Sciences and Management Innovation Foundation of Northwestern Polytechnical University.