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