车间调度问题可借助遗传算法来解决

本文讨论的任务车间调度问题是一个典型的NP完全问题，也是最难解的组合优化问题之一。虽然本题给出的工件（墙纸）数n、机器数m及工序（印刷颜色）数l较小，但可以看到，利用经典整数规划的方法求解该问题还是存在着约束条件不够，结果不容易收敛的问题，并且当n，m，l偏大时采用全局搜索的办法来处理该问题是不切实际的。在实际生产中，JSP并不总是要求得到精确解，因此有研究者使用近似算法在适当的时间内得到一个可接受的近似最优解来求解此问题，实际的计算表明，好的近似算法通常能在可接受的时间内得到与精确解相差甚小的近似解，甚至对于大部分的实例，近似算法能得到与精确最优解一致的近似解。因此，本文采用近似算法中的遗传算法（Genetic Algorithms，GA）求解任务调度问题。