单机订单接受与加工调度问题的拉格朗日松弛算法

• 作者: 王秀利 谢杏子
• 来源期刊: 系统管理学报
• 学科: 工学
• 关键词: 订单接受 调度 拉格朗日松弛 准备时间
• 年，卷（期）: 2020,（5）
• 页码范围: 874-881
• 页数: 8页
• 分类号: TP391
• 语种: 中文
• DOI: 10.3969/j.issn1005-2542.2020.05.005

摘要

针对不同类型订单加工切换时机器需要准备时间的实际生产情况,研究了单机订单接受与加工调度优化决策问题,旨在最大化企业净收益.鉴于研究问题的强NP难属性,设计了基于拉格朗日松弛理论的启发式算法.首先,该算法通过加入相邻订单相异性约束以提高松弛解质量;其次,应用动态规划递推公式求解拉格朗日松弛问题;最后,利用问题的优化性质并基于贪婪规则构造原问题可行解.不同规模问题的实验结果表明,该算法能在合理计算时间内得到满意的近优解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王秀利		11	30	3.0	5.0
2	谢杏子		1	0	0.0	0.0