调度问题是制造流程规划和管理中最关键的问题之一。
这个领域最困难的问题之一是作业车间调度问题(Job-shop Scheduling Problem, JSP),该问题中,一组机器需处理一组工件,每个工件由一系列具有先后顺序约束的工序形成,每个工序只需要一台机器,机器一直可用,可以一次处理一个操作而不会中断。决策内容包括如何对机器上的工序进行排序,已优化给定的性能指标。JSP的典型性能指标是完工时间 (makespan),即完成所有工作所需的时间。JSP是一个众所周知的NP难题。
柔性作业车间调度问题(Flexible Job-shop Scheduling Problem, FJSP)是经典JSP的拓展,该问题中每个工序允许在一组可用机器中的任何一个上进行处理。FJSP比传统的JSP更难,因为它引入了除了排序之外的另一个决策内容,即作业路径。确定作业路径意味着为每个工序决定使用哪台机器处理它。
下面是一个例子:
在这个例子中,有3个工件,它们分别具有2,3,1个工序。工件1的工序2(O1,2 )可被2台机器处理,并且在机器3上处理的时间为t1,2,3 = 5.