Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times

Name: Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times
Author: Yanıkoğlu, İhsan, Yavuz, Tonguç

İsim	Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times
Yazar	Yanıkoğlu, İhsan, Yavuz, Tonguç
Basım Tarihi:	2022-09-16
Basım Yeri	- Elsevier
Konu	Branch-and-price, Integer programming, Parallel machine scheduling, Robust optimization, Robust optimization
Tür	Süreli Yayın
Dil	İngilizce
Dijital	Evet
Yazma	Hayır
Kütüphane:	Özyeğin Üniversitesi
Demirbaş Numarası	0377-2217
Kayıt Numarası	9ee8784c-8478-4245-b228-847efdd4718f
Lokasyon	Industrial Engineering
Tarih	2022-09-16
Notlar	Home Appliances Department of the Vestel Electronics Company
Örnek Metin	This paper studies a machine scheduling problem that minimizes the worst-case total tardiness for unrelated parallel machines with sequence-dependent setup and uncertain processing times. We propose a robust optimization reformulation of the related machine scheduling problem and discuss several important properties of the mathematical model and the reformulation approach. The proposed model generalizes robust parallel machine scheduling problems by including sequence-dependent setup times and ellipsoidal uncertainty sets. Another key contribution of the paper is to show that scheduling problems usually have alternative optimal solutions for the worst-case tardiness objective, whose performance under nominal processing times may vary or vice a versa. This issue has been addressed by studying the Pareto efficient extensions of the proposed robust optimization models to provide solutions that are immune to changes in processing times. A branch-and-price algorithm has been developed to solve realistically sized instances in less than one hour, which a commercial solver cannot achieve. Numerical results show the effectiveness of the proposed approach since realistically sized instances such as (4 machines, 32 jobs) and (150 machines, 300 jobs) can be solved to optimality within the time limit, and the (average) objective function value improvement made by the robust approach can get as high as 56% compared with the (nominal) optimal solutions that ignore uncertainty in problem data.
DOI	10.1016/j.ejor.2021.11.023
Cilt	301

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times

Yazar Yanıkoğlu, İhsan, Yavuz, Tonguç

Basım Tarihi 2022-09-16

Basım Yeri - Elsevier

Konu Branch-and-price, Integer programming, Parallel machine scheduling, Robust optimization, Robust optimization

Tür Süreli Yayın

Dil İngilizce

Dijital Evet

Yazma Hayır

Kütüphane Özyeğin Üniversitesi

Demirbaş Numarası 0377-2217

Kayıt Numarası 9ee8784c-8478-4245-b228-847efdd4718f

Lokasyon Industrial Engineering

Tarih 2022-09-16

Notlar Home Appliances Department of the Vestel Electronics Company

Örnek Metin This paper studies a machine scheduling problem that minimizes the worst-case total tardiness for unrelated parallel machines with sequence-dependent setup and uncertain processing times. We propose a robust optimization reformulation of the related machine scheduling problem and discuss several important properties of the mathematical model and the reformulation approach. The proposed model generalizes robust parallel machine scheduling problems by including sequence-dependent setup times and ellipsoidal uncertainty sets. Another key contribution of the paper is to show that scheduling problems usually have alternative optimal solutions for the worst-case tardiness objective, whose performance under nominal processing times may vary or vice a versa. This issue has been addressed by studying the Pareto efficient extensions of the proposed robust optimization models to provide solutions that are immune to changes in processing times. A branch-and-price algorithm has been developed to solve realistically sized instances in less than one hour, which a commercial solver cannot achieve. Numerical results show the effectiveness of the proposed approach since realistically sized instances such as (4 machines, 32 jobs) and (150 machines, 300 jobs) can be solved to optimality within the time limit, and the (average) objective function value improvement made by the robust approach can get as high as 56% compared with the (nominal) optimal solutions that ignore uncertainty in problem data.

DOI 10.1016/j.ejor.2021.11.023

Cilt 301