智能优化算法-JSSP描述

一个典型的作业调度问题的提法为：一个加工系统中有m台机器和n个待加工的工件，所有工件的加工路径（即技术约束条件）预先给定，但不要求一致，各工件在各机器上的操作时间已知。调度的任务是如何合理安排每台机器上工件的加工次序，使约束条件得到满足，同时使某些性能指标得到优化。一般需要满足以下两个约束：①工件i的第j道工序必须在第j-1道工序完咸后才能开始，即顺序约束；②同一时刻，一台机器只能加工一个工件，进行一道工序的操作，即资源约束。

具体地，用J=｛1，2，…，n）表示工件集，M=｛1，2，…，m｝表示机器集，O=｛0，l，…，n×m，n×m+1｝表示所有工序的集合，其中，0和n×m+1分别表示虚拟的开始和结束操作，其中的每个工序是和顺序约束相关的.对于每个工序j，只能在它的前序工序集Pi中的所有工序均已被加工完成，并且加工工序j的机器为空闲时，才可以进行调度加工.用Ti表示工序j的加工时间，Fi表示工序j的完工时间，A（t）表示在t时刻正被加工的工序集.如果工序j需要在机器m加工，则表示为ejm=l，否则ejm=0。则最小化最终完工时间的调度问题，可以用以下模型阐述：

目标函数（4.23）最小化最后一个工序的完工时间，即makespan。约束（4.24）保证工序之间的约束关系。约束（4.25）表示每个机器同一时刻只能加工一个工序。约束（4.26）保证工序的完工时间是非负的，确保所有工序都被完成。

在典型的Job Shop调度问题中，除技术约束外，通常还假定以下条件：各工件经过其准备时间后即可开始加工；每一时刻每台机器只能加工一个工序且每个工序只能被一台机器所加工，同时加工过程为不间断，整个加工过程中机器均有效；整个加工过程中，每个工件不能在同一台机器上加工多次；各工件必须按工艺路线以指定的次序在机器上加工；不考虑工件加工的优先权；操作允许等待，即前一个操作未完成，则后面的操作需要等待；所有机器处理的加工类型均不同；除非特殊说明，工件的加工时间事先给定且在整个加工过程中保持不变；除非特殊说明，工件加工时间内包含加工设置时间。

JSSP的求解要远远复杂于旅行商问题和流水线作业调度问题，其原因在于：

（1）解空间容量巨大，n个工件、m台机器的问题包含（n！）m种排列，即使对于Fisher-Thompson10×10问题，解空间就达到3.96×1065，若用每秒运算1亿次的计算机，遍历解空间需要1.26×1050年；(www.xing528.com)

（2）调度解的编码复杂且多样性，算法的搜索操作多样化；

（3）存在工艺技术约束条件的限制，必须考虑解的可行性；

（4）调度指标的计算相对算法的搜索比较费时；

（5）优化超曲面缺少结构信息，通常复杂且存在多个分布无规则甚至彼此相邻的极小。