并行机生产与具有等待时间限制的成批运输协调调度问题
来源期刊：控制与决策2011年第6期
论文作者：宫华 唐立新
文章页码：921 - 924
关键词：并行机;成批运输;复杂性;最坏情况;
摘 要：研究了运输阶段具有等待时间限制的成批运输与并行机生产协调调度问题,目标为最小化制造期与运输费用之和.通过复杂性分析,证明其是强NP难问题,提出启发式算法并证明其最坏情况性能比为4-1/m.当一个运输批必须在同一台机器加工时,证明其也是强NP难问题.将加工时间与等待时间限定值进行比较,分别提出两个启发式算法,并证明其最坏情况性能比分别为2-1/m和4-1/m.
宫华1,2，唐立新2
1. 沈阳理工大学理学院2. 东北大学信息科学与工程学院
摘 要：研究了运输阶段具有等待时间限制的成批运输与并行机生产协调调度问题,目标为最小化制造期与运输费用之和.通过复杂性分析,证明其是强NP难问题,提出启发式算法并证明其最坏情况性能比为4-1/m.当一个运输批必须在同一台机器加工时,证明其也是强NP难问题.将加工时间与等待时间限定值进行比较,分别提出两个启发式算法,并证明其最坏情况性能比分别为2-1/m和4-1/m.
关键词：并行机;成批运输;复杂性;最坏情况;
