摘要
研究了一类具有准备时间和移出时间约束的单服务器并行机调度问题.这个问题概括了工件仅需要准备操作的经典单服务器并行机调度问题.在该问题中,服务器不仅需要在每个工件加工之前将其装载到一台机器上,而且在工件加工结束后,将其从机器上卸载下来,装载和卸载操作需要一定的时间.目标函数为最小化最大完工时间.主要研究指定机器加工的情况,针对这种情况,构建了多项式时间内可解的启发式算法.该启发式的值与最优值的比值为2,且证明了该界为紧界.
The scheduling parallel machines with a single sever is investigated, as well as additional constraints on setups and removals. It generalizes classical parallel machine scheduling problem with a single server which needs to perform setup operation of each job only. The single server in this problem does not only load a job on a machine which takes a certain setup time immediately before processing but also unloads a job from the machine which takes a certain removal time after processing. The objective is to minimize makespan. A heuristic algorithm is constructed for the problem concerning the situations, with dedicated machine. A polynomial time approximate algorithm is proposed with a tight worst-case bound at most twice as large as the optimal value.
出处
《沈阳大学学报（自然科学版）》
CAS
2012年第4期66-69,2,共4页
Journal of Shenyang University：Natural Science
基金
2011年辽宁省教育厅科学研究一般项目(L2011207)
关键词
调度
并行机
单服务器
NP-难
启发式
scheduling
parallel machines
single server
NP-hard problem
heuristics
