柔性作业车间调度问题介绍 (Flexible Job-shop Scheduling Problem, FJSP)

调度问题是制造流程规划和管理中最关键的问题之一。

这个领域最困难的问题之一是作业车间调度问题(Job-shop Scheduling Problem, JSP),该问题中,一组机器需处理一组工件,每个工件由一系列具有先后顺序约束的工序形成,每个工序只需要一台机器,机器一直可用,可以一次处理一个操作而不会中断。决策内容包括如何对机器上的工序进行排序,已优化给定的性能指标。 JSP的典型性能指标是完工时间 (makespan),即完成所有工作所需的时间。 JSP是一个众所周知的NP难题。

柔性作业车间调度问题(Flexible Job-shop Scheduling Problem, FJSP)是经典JSP的拓展,该问题中每个工序允许在一组可用机器中的任何一个上进行处理。FJSP比传统的JSP更难,因为它引入了除了排序之外的另一个决策内容,即作业路径。确定作业路径意味着为每个工序决定使用哪台机器处理它。

FJSP可被定义为:

  • n个工件,用i索引,这些工件彼此互相独立。第i个工件用J_i表示。
  • 每个工件J_il_i个工序,和一系列顺序约束P_i.
  • 每个工件i的工序用O_{i,j},j=1,\ldots,l_i表示。
  • m个机器,用k索引。
  • 对于每个工序O_{i,j},都有一系列机器M_{i,j},M_{i,j} \subseteq {1,\ldots,m}有能力加工它。
  • 工件O_{i,j}在机器k上的处理时间是给定的,并且用t_{i,j,k}表示。
  • 每个工序在加工时都不能被中途打断。
  • 一个机器在任何时间最多能够处理一个工件。

下面是一个例子:

M_1 M_2 M_3
O_{1,1} 7 7 5
O_{1,2} 8 5
O_{2,1} 5
O_{2,2} 3 4
O_{2,3} 7 6 3
O_{3,1} 1 2

在这个例子中,有3个工件,它们分别具有2,3,1个工序。工件1的工序2(O_{1,2})可被2台机器处理,并且在机器3上处理的时间为t_{1,2,3} = 5.

发表评论

电子邮件地址不会被公开。 必填项已用*标注