Optimal cyclic scheduling of a hoist and multi-type parts with fixed processing times

Ada Che, Pengyu Yan, Naiding Yang, Chengbin Chu

Research output: Contribution to journalArticlepeer-review

42 Scopus citations

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.

Original languageEnglish
Pages (from-to)1225-1243
Number of pages19
JournalInternational Journal of Production Research
Volume48
Issue number5
DOIs
StatePublished - Jan 2010

Keywords

  • Branch and bound algorithm
  • Cyclic hoist scheduling
  • Fixed processing times
  • Multi-type parts
  • No-wait

Fingerprint

Dive into the research topics of 'Optimal cyclic scheduling of a hoist and multi-type parts with fixed processing times'. Together they form a unique fingerprint.

Cite this