一类带有安装时间的单机成组排序问题

摘要

针对一类带有准备时间和安装时间的单机成组排序问题,给出了求解最优排序的多项式算法.其中每个工件都具有自己的准备时间,组和组之间具有安装时间,并且安装时间和已经加工完工件的加工时间有关.所有工件在机器上加工时,一次只能加工一个工件,工件不可中断,组内工件连续加工,组和组之间需要安装时间.对目标函数为极小化最大完工时间的单机成组排序问题,给出了求解最优排序的多项式算法.原问题不是成组问题,为此在原问题的基础上添加了工件的成组问题且组内每个工件都具有自己准备时间,其结果是依然能给出求解最优排序的多项式算法.