论文部分内容阅读
讨论了加工时间依赖开工时间的Flow shop调度问题.在这类问题中,工件的加工时间是开工时间的简单线性函数,机器间满足某种优势关系.对于这类问题,当目标函数是极小化最大完工时间时,尽管比相应的经典问题复杂,但仍存在多项式算法.如果目标函数是极小化加权完工时间和或极小化最大延误,则经典问题中的结论未必成立.