基于Benders分解和分枝定界的随机交期批量流流水车间调度  

Stochastic Due-Date Lot-Streaming Flowshop Scheduling with Benders Decomposition and Branch-and-Bound

作　　者：石亚东 刘冉[1] 王铖恺 吴泽锐 SHI Yadong;LIU Ran;WANG Chengkai;WU Zerui(School of Mechanical Engineering,Shanghai Jiao Tong University,Shanghai 200240,China)

机构地区：[1]上海交通大学机械与动力工程学院,上海200240

出　　处：《上海交通大学学报》2024年第8期1271-1281,I0001,I0002,共13页Journal of Shanghai Jiaotong University

基　　金：上海市科委“科技创新行动计划”高新技术领域项目(22511103603)。

摘　　要：针对交期随机的批量流车间调度问题,以最小化工件延期期望之和为目标,推导出工件交期符合3类经典随机分布条件下问题目标的闭式计算表达式.建立考虑换模时间与随机交期的问题数学模型,针对模型高度非线性特征对其线性化.设计一种基于逻辑的Benders分解(LBBD)与分枝定界相结合的优化算法,提出两种有效加速策略提升算法求解效率.数值实验结果验证了算法的有效性,通过随机交期与确定交期结果的比较,验证了考虑随机的必要性.The lot-streaming flowshop scheduling problem with stochastic due time is addressed in this paper,with the objective of minimizing the sum of expected job delays.Closed-form expressions for the expected delays of jobs are derived under three classical distribution conditions.A mathematical model is then formulated,considering set-up times and stochastic due time.To address the highly nonlinear nature of the model,a linearization is performed.Furthermore,an optimization algorithm is designed using a Logic-based Benders decomposition(LBBD)approach combined with branch-and-bound.Two effective acceleration strategies are introduced to improve the efficiency of the algorithm.The numerical experiments demonstrate the effectiveness of the proposed algorithm,and the necessity of considering stochastic lead times is verified by comparing the results with those obtained from deterministic due time.

关 键 词：随机交期 批量流 Benders分解 分枝定界 

分 类 号：TH186[机械工程—机械制造及自动化]