一个常见的调度问题是作业车间调度问题,多个作业在多台机器上处理。每个作业由一系列任务组成,这些任务必须按照给定的顺序执行,并且每个任务必须在特定的机器上处理。例如,作业可以是制造单一的消费品,如汽车。问题是如何安排机器上的任务,以最小化调度的长度,即所有任务完成所需的时间。
作业车间问题由几个约束条件:
- 在作业的前一个任务完成之前,作业的任何任务不能启动
- 一台机器一次自能做一项任务
- 一项任务,一旦开始,必须运行到完成
例子
下面是一个作业车间调度问题的简单例子,其中每个作业都用一对数字(m, p)来表示,其中m是必须处理该任务的机器编号,p是该任务的处理时间。(作业和机器的编号从0开始)
- job 0 = [(0, 3), (1, 2), (2, 2)]
- job 1 = [(0, 2), (2, 1), (1, 4)]
- job 2 = [(1, 4), (2, 3)]