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

摘要

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