含有批处理机的三机流水作业加工总长问题在某些情形下的强NP困难性

摘要

本文研究含有批处理机的三台机器流水作业加工总长问题在某些情形下的计算复杂性.在批处理机上同时加工的工件组成一个工件批,一个工件批的所有工件同时开始、同时结束.当批处理机的容量有限时,我们证明了下列情形为强NP困难的:第一台机器是批处理机、其余两台机器是单机;第二台机器是单机、其余两台机器是批处理机;第三台机器是批处理机、其余两台机器是单机.