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

柔性作业车间调度问题定义

JSP比传统的JSP更难，因为它引入了除了排序之外的另一个决策内容，即作业路径。确定作业路径意味着为每个工序决定使用哪台机器处理它。FJSP可被定义为：

有个工件，用索引，这些工件彼此互相独立。第个工件用表示。

每个工件有个工序，和一系列顺序约束.

每个工件的工序用表示。

有个机器，用索引。

对于每个工序，都有一系列机器有能力加工它。

工件在机器上的处理时间是给定的，并且用表示。

每个工序在加工时都不能被中途打断。

一个机器在任何时间最多能够处理一个工件。

图1

举例2

图2

遗传算法解决柔性作业调用问题

柔性作业车间调度问题 (FJSSP)是组合优化和生产管理领域很重要的研究课题，它是经典的作业车间调度问题 (JSSP)的延伸且被认为是强NP-hard问题。在FJSSP中，同一个工序的加工机器可能有多台。FJSSP由两个子问题组成，第一个子问题是将一系列可选的机器分配给指定的工序，第二个子问题是计算分配给指定机器的工序序列的完工时间。虽然比JSSP仅多了一个将一系列可选机器分配给指定工序的步骤，但是为解决FJSSP在染色体编码、解码、交叉和变异方面要做出相当大的改进，因此，解决FJSSP的难度要大得多。

FJSSP描述

相比每道工序被特定的某台机器加工的JSSP，FJSSP的任务分配要更具挑战性，它的每道工序的加工机器可能有不止一台可供选择，在本文中FJSSP由以下元素组成：
工件集：J={J1,J2,J3,… … …,Jn}是要被排程的大小为n的独立工件集，每个工件Ji由一系列按顺序依次加工的工序{Oi1,Oi2,Oi3,… … …,Oin}组成，所有的工件在时刻0都是可以被加工的。
机器集：M={M1,M2,… … …,Mm}是大小为m的机器集合，每个机器仅可以一次加工一个工件，所有机器在时刻0是可以加工工件的。
柔性：通常FJSSP的柔性可以分成如下两类，每道工序可以被m台机器中任意一台加工的整体柔性和每道工序可以被m台机器的一个子集中的任意一台机器加工的部分柔性。
对FJSSP的其它假设：每道工序每次只可以被一台机器加工；每道工序的处理时间因机器而异且不同的机器是相互独立的；每道加工工序是不可中断的；加工某工件的机器准备时间已被考虑在相应的加工时间里；工件在不同机器间的转移时间已被考虑在加工时间里。
目标：针对实际的生产需要，这里考虑的是最基础、最典型的最大完工时间这一性能指标Cmax(Makespan)。FJSSP的目标是将每个工件分配到某台合适的机器上进行加工并对机器的加工序列进行排程以使得完成所有工件加工任务的最大完工时间Cmax最小。对n个工件、m台机器的柔性作业调度问题，设Ci是工件Ji的完工时间，求最大完工时间Cmax最小值的目标函数为
Cmax = min {max Ci, i=1,…n}

遗传算法简介

遗传算法是一种解决大规模计算问题的全局搜索方法，它是受自然界中生物进化的启发而提出的。通常，被解决问题的一个解被称作一条染色体或一个个体，每个个体都有自己的适应度值。通过全局搜索(GS)、局部搜索(LS)相结合的方式来生成初始种群的大部分个体，再通过随机搜索(RS)来生成部分个体以增加种群的基因多样性。遗传算法以迭代的方式运行，每迭代一次代表了种群的一代。通过交叉、变异来搜索尽可能多的尽可能优秀的解，通过适应度计算和选择来选择更优秀的个体，进而完成一代的进化。一直重复这种搜索过程，直到在时间或求解质量方面满足给定条件为止。