设有n项任务,加工时间分别表示为正整数【图片】。现有2台同样的机器,从0时刻可以安排对这些任务的加工。规定只要有待加工的任务,任何机器就都不得闲置。如果直到时刻t所有任务都完成了,总的加工时间就等于t。设计一个算法找到使得总加工时间t达到最小的调度方案。令【图片】那么存在一个最优调度使得第一台机器上总加工时间不超过T,且达到最大. 该问题称为双机调度问题。假设问题的【图片】,其中【图片】. 如果【图片】,那么第i项任务放到第一台机器上加工;如果【图片】,那么第i项任务放到第二台机器上加工。从问题本质看,任务的加工时间相当于0-1背包问题中的下述输入参数: