SPEAKER: Chengbin Chu (储诚斌), Université Gustave Eiffel, ESIEE Paris and COSYS-Grettia Laboratory

TIME/DATE: 2024.11.18 14:00

CLASSROOM: A305

ABSTRACT

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.

GUEST BIO

储诚斌教授现为法国艾菲尔大学教授，中国教育部2004年度“长江学者”讲座教授，

他毕业于合肥工业大学，于 1990年以优异成绩获得梅斯大学博士学位，1992年被聘为法国国家信息及自动化研究院终身研究员。他于1995年取得独立指导博士生资格。1996年入盟特鲁瓦工业大学并负责创建和领导工业系统优化实验室。2008至2017年在巴黎中央理工大学（现巴黎-萨克雷大学中央理工-高等电力学院）, 主持由家乐福﹑达能﹑路易威登、赛峰、标致雪铁龙集团等跨国公司赞助的供应链管理讲席职位。

储教授的研究领域集中在生产和物流系统的优化，包括采购管理、可靠性分析与配置、系统维护策略优化、交通运输、下料与装箱等方面。迄今为止，他已发表专著3部，240多篇文章被OR、EJOR、Transportation Science等国际期刊发表或接收。其中两篇文章荣获相关期刊的最佳论文奖，3篇论文在国际学术会议获奖。他承担过20多项由欧盟、法国中央和地方政府或企业资助的研究项目，总经费近1000万欧元。他的研究成果在数十家各种规模和不同行业的企业得到应用，并创造巨大经济和社会效益。由于他在理论创新及实际应用方面的突出贡献，他早在1996年就荣获法国运筹学和辅助决策领域旨在鼓励理论创新并将其应用于解决实际问题的最高奖项Robert Faure一等奖。

储教授先后担任三本IEEE Transactions期刊副编，现为CIE 和IJPR 两本期刊的编委。他先后以长江学者、海外讲座教授、兼职教授、外籍专家等身份同合肥工业大学、西安交通大学、西北工大、同济大学等中国高校合作，并担任杰出青年基金、长江学者等项目的评审专家。