谢　谢,吴星瑶,李晓丽,孔祥玉

(1.沈阳大学装备制造综合自动化重点实验室,辽宁沈阳　110044;

2.浙江大学计算机科学与技术学院,浙江杭州310058;3.吉林省双辽市职业高级中学,吉林双辽136400)



带有不可用区间、工件可拒绝的单机生产与运输协调调度问题

谢谢1,吴星瑶2,李晓丽3,孔祥玉1

(1.沈阳大学装备制造综合自动化重点实验室,辽宁沈阳110044;

2.浙江大学计算机科学与技术学院,浙江杭州310058;3.吉林省双辽市职业高级中学,吉林双辽136400)

摘要:从生产实际提炼出一类单机生产与运输协调调度问题,即当工件在机器加工结束后由一辆容量受限的车运到配送中心.与经典调度问题不同的是,加工机器带有不可用区间,且可以拒绝加工某些工件,但拒绝产生惩罚.目标函数是最后一批完工工件到达配送中心的时间与拒绝工件的惩罚和.由于该问题是NP-难的,提出了一个多项式时间内可解的启发式算法,并证明该算法的最坏性能比为6.

关键词:调度; 不可用区间; 拒绝工件; 启发式算法

传统的生产调度和运输调度是分开研究的,通常都是将生产放在首要位置而运输放在一个从属的地位,即先安排生产调度,然后再相应进行运输物流调度.然而在实际生产中,由于运输工具数量和能力的限制,而使工序之间物料的传递受到了限制,在不考虑运输情况的生产调度即使是最优调度也难以有效的执行.所以将生产调度和运输物流调度协调进行研究,有助于提高运输工……