Back to Search

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

Title	Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times
Author	Yanıkoğlu, İhsan, Yavuz, Tonguç
Publication Date:	2022-09-16
Publication Place	- Elsevier
Subject	Branch-and-price, Integer programming, Parallel machine scheduling, Robust optimization, Robust optimization
Type	Periodical
Language	English
Digital	Yes
Manuscript	No
Library:	Özyeğin University
Library Asset ID	0377-2217
Record ID	9ee8784c-8478-4245-b228-847efdd4718f
Library Location	Industrial Engineering
Date	2022-09-16
Notes	Home Appliances Department of the Vestel Electronics Company
Sample Text	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

View in source Özyeğin University Özyeğin University - Historical works, archives, and periodicals search engine

Özyeğin University

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

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

Publication Date 2022-09-16

Publication Place - Elsevier

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

Type Periodical

Language English

Digital Yes

Manuscript No

Library Özyeğin University

Library Asset ID 0377-2217

Record ID 9ee8784c-8478-4245-b228-847efdd4718f

Library Location Industrial Engineering

Date 2022-09-16

Notes Home Appliances Department of the Vestel Electronics Company

Sample Text 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