【讲座名称】

An efficient branch-and-price algorithm to solve parallel machine scheduling with machine usage costs

【主讲人】

储诚斌教授

【主讲人介绍】

储诚斌教授现为法国艾菲尔大学教授。他1985年毕业于合肥工业大学电气工程系，1990年以优异成绩获得梅斯大学博士学位，1992年被聘为法国国家信息及自动化研究院（INRIA）终身研究员。他于1996年入盟特鲁瓦工业大学并负责创建和领导工业系统优化实验室（LOSI）。2008至2017年在巴黎中央理工大学（现巴黎-萨克雷大学中央理工-高等电力学院），主持由家乐福﹑达能﹑路易•威登（LV）、赛峰（SAFRAN）、标致-雪铁龙集团等跨国公司赞助的供应链管理讲席职位。迄今为止，他已发表专著3部，280多篇文章被OR、EJOR、Transportation Science、Transportation Research (Parts B & E)、IEEE Transactions、SIAM Journal on Computing等国际期刊发表或接收。其中两篇文章荣获相关期刊的最佳论文奖，3篇论文在国际学术会议获奖。储教授先后担任三本IEEE Transactions期刊副编，现为IJPR的编委。。

【讲座内容简介】

In this talk, we consider unrelated parallel machine scheduling involving machine usage costs, in addition to classic job completion time-related costs. The usage cost of each machine is made up of a fixed cost and a variable cost proportional to the total processing time of the jobs assigned to it. These features model many practical situations where machine usage costs include, for example, rental fees when the machines are not owned but rented.

To tackle this problem, four mathematical models based on the Shortest Weighted Processing Time (SWPT) rule are introduced. Additionally, the problem is formulated into a set-partitioning model, for which a branch-and-price algorithm is proposed with an appropriate branching strategy. This facilitates the development of an efficient pseudo-polynomial dynamic programming algorithm and a polynomial-time heuristic to solve the pricing problem.

Extensive numerical experiments demonstrate the superior performance of the proposed branch-and-price algorithm over the four SWPT-based mathematical formulations and an existing branch-and-price algorithm designed for a special case. Notably, it can optimally solve instances involving up to 225 jobs and 15 machines within one hour. Moreover, statistical analyses reveal that the proposed polynomial-time heuristic significantly reduces the computation time, and the mathematical model based on the contribution of every job to the total weighted completion time exhibits the best overall performance.

【时间】

2026年5月7日（周四）上午10:00

【地点】

犀浦校区交通运输与物流学院417学术报告厅

主办：研究生院 交通运输与物流学院

承办：物流管理系 物流工程系 教工物流党支部 学院学工组 交通运输科技协会

邀请人：甘蜜教授