报告题目：A flow-based formulation for parallel machine scheduling using decision diagrams

报告所属学科：管理科学与工程

报告人：Roel Leus（鲁汶大学）

报告时间：2023年11月11日 10:30-12:30

报告地点：经管学院704室

报告摘要：

This work presents a new flow-based formulation for identical parallel machine scheduling with a regular objective function and without idle time. The formulation is constructed with the help of a binary decision diagram that represents all job sequences that respect specific ordering rules. These rules rely on a partition of the planning horizon into, generally non-uniform, periods and do not exclude all optimal solutions, but they constrain solutions to adhere to a canonical form. The new formulation has numerous variables and constraints, and hence a Dantzig-Wolfe decomposition is applied in order to compute the linear programming relaxation in reasonable time; the resulting lower bound is stronger than the bound from the classical time-indexed formulation. A branch-and-price framework based on the new formulation is developed, which can solve many instances faster than before. Compared with the state-of-the-art procedure by means of a series of computational experiments, the proposed formulation seems to perform better especially with a larger number of machines.

报告人简介：

Roel Leus is a professor of the Department of Operations Research and Statistics Research, Faculty of Economics and Business, KU Leuven. He currently serves as the program director for the Business Engineering programs of his faculty, and also associate editor of the journal OR Spectrum. His research interests are diverse in the field of operations research and operations management, in particular sequencing and scheduling, project planning and scheduling, planning and scheduling under uncertainty, project management, combinatorial optimization, decision making under uncertainty. Up to now, Prof. Roel has published over 80 papers in international journals such as Production and Operations Management, INFORMS Journal on Computing, IIE Transactions, Decision Sciences, Naval Research Logistics, European Journal of Operational Research, Journal of Scheduling, etc.