带有机器维修和工件派送的单机排序问题

• 作者: 蔡伟 杨梅
• 来源期刊: 青海师范大学学报（自然科学版）
• 关键词: 单机排序 机器维修 工件派送 近似算法 最坏情况分析
• 年，卷（期）: 2021,（1）
• 页码范围: 19-25
• 页数: 7页
• 分类号: O22
• 语种: 中文
• DOI: 10.3969/j.issn.1001-7542.2021.01.004

摘要

研究了带有机器维修和工件派送的单机排序问题,该问题可以被视为一个集成生产和出站配送的排序模型.不同体积的工件需要在带有一个维修区间的机器上加工,且加工不可中断,然后由固定容量的车辆批次交付给顾客,车辆派送完一批后需要返回派送中心交付下一个批次,工件派送到不同客户处所需的时间不同.目标函数是最小化最大完工时间.本文主要研究工件加工完成后由单车辆派送到多顾客的情形,提出了5/2-近似算法;对单客户的特殊情况该算法的界是2且是紧界.