期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 290, 期 2, 页码 469-478出版社
ELSEVIER
DOI: 10.1016/j.ejor.2020.08.032
关键词
Scheduling; Lexicographic optimization; Exact MILP methods; Robust optimization; Price of robustness
资金
- Engineering and Physical Sciences Research Council Research (EPSRC) [EP/M028240/1, EP/P016871/1]
- EPSRC [EP/P016871/1, EP/K040723/1, EP/M028240/1] Funding Source: UKRI
This study investigates the minimum makespan scheduling problem in industrial resource allocation, proposing a two-stage robust scheduling approach based on exact lexicographic scheduling and approximate rescheduling. The analysis is substantiated by parameterizing the price of robustness and utilizing lexicographic optimality for efficient rescheduling. Additionally, a lexigographic branch-and-bound algorithm is introduced for optimal substructure and computational validation.
In industrial resource allocation problems, an initial planning stage may solve a nominal problem instance and a subsequent recovery stage may intervene to repair inefficiencies and infeasibilities due to uncertainty, e.g. machine failures and job processing time variations. In this context, we investigate the minimum makespan scheduling problem, a.k.a. P vertical bar vertical bar C-max, under uncertainty. We propose a two-stage robust scheduling approach where first-stage decisions are computed with exact lexicographic scheduling and second-stage decisions are derived using approximate rescheduling. We explore recovery strategies ac- counting for planning decisions and constrained by limited permitted deviations from the original schedule. Our approach is substantiated analytically, with a price of robustness characterization parameterized by the degree of uncertainty, and numerically. This analysis is based on optimal substructure imposed by lexicographic optimality. Thus, lexicographic optimization enables more efficient rescheduling. Further, we revisit state-of-the-art exact lexicographic optimization methods and propose a lexicographic branchand-bound algorithm whose validated computationally. (C) 2020 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据