Unrelated parallel machine scheduling problem with stochastic sequence dependent setup times

Saraç T., Özçelik F., Ertem M.

Operational Research, vol.23, no.3, 2023 (SCI-Expanded) identifier

  • Publication Type: Article / Article
  • Volume: 23 Issue: 3
  • Publication Date: 2023
  • Doi Number: 10.1007/s12351-023-00789-3
  • Journal Name: Operational Research
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, IBZ Online, ABI/INFORM, Aerospace Database, zbMATH, Civil Engineering Abstracts
  • Keywords: Genetic algorithm (GA), Stochastic sequence-dependent setup times, Two-stage stochastic programming, Unrelated parallel machine scheduling problem
  • Eskisehir Osmangazi University Affiliated: Yes


Unrelated parallel machine scheduling problem (UPM) is widely studied in the scheduling literature because of its extensive application area in the industry. Since it has a stochastic nature, several studies handled the problem as stochastic. However, most of the studies that have considered the problem as stochastic focused only on the case of stochastic processing times. Whereas, especially in industries where setup times are sequence and machine-dependent, these are often stochastic, as well. Although this situation has been ignored in the literature for a long time, it has been examined only in a few studies. In this study, for the first time, an exact solution method is proposed to solve UPM with stochastic sequence-dependent setup times (SDSTs). For the considered problem, a two-stage stochastic programming method is proposed. A mathematical model and a genetic algorithm are developed for the stochastic problem. The effectiveness of the proposed solution approaches is demonstrated using randomly generated test problems. The test results demonstrate the importance of considering the SDSTs as stochastic.