Optimal cyclic scheduling of a hoist and multi-type parts with fixed processing times
- 1 December 2008
- journal article
- research article
- Published by Taylor & Francis in International Journal of Production Research
- Vol. 48 (5) , 1225-1243
Abstract
This paper proposes an exact algorithm to solve a cyclic hoist scheduling problem in a printed circuit board (PCB) electroplating facility, where multi-type parts with fixed processing times are processed in the same time and the parts are not allowed to wait in the tanks or on the hoist. Finding an optimal schedule in such a production line is equivalent to finding two types of related sequences: part input sequence and hoist move sequence. We show that the entering times of the parts are the decision variables of the problem. We formulate our problem using the notion of prohibited intervals and solve it by enumerating the non-prohibited intervals of the decision variables. This enumeration is accomplished more efficiently with a dynamic branch and bound procedure, which utilises relaxed solutions to eliminate redundant non-prohibited intervals in the search process. The proposed algorithm is polynomial in the number of tanks if the number of part types is fixed, but exponential if it is arbitrary. Computational results on randomly generated test instances indicate that the algorithm is effective.Keywords
This publication has 30 references indexed in Scilit:
- A faster polynomial algorithm for 2-cyclic robotic schedulingJournal of Scheduling, 2006
- Cyclic hoist scheduling in large real-life electroplating linesOR Spectrum, 2006
- Sequencing and Scheduling in Robotic Cells: Recent DevelopmentsJournal of Scheduling, 2005
- Single-track multi-hoist scheduling problem: a collision-free resolution based on a branch-and-bound approachInternational Journal of Production Research, 2004
- A polynomial algorithm for 2-degree cyclic robot schedulingEuropean Journal of Operational Research, 2003
- Multicyclic hoist scheduling with constant processing timesIEEE Transactions on Robotics and Automation, 2002
- Metaheuristics for the Stochastic Hoist Scheduling Problem (SHSP)International Journal of Production Research, 2001
- Part sequencing in three-machine no-wait robotic cellsOperations Research Letters, 2000
- Cyclic scheduling of a hoist with time window constraintsIEEE Transactions on Robotics and Automation, 1998
- Sequencing of Parts in Robotic CellsInternational Journal of Flexible Manufacturing Systems, 1997