方 霞， 俞宏图， 熊 齐

（湖南文理学院， 国家Linux 技术培训与推广中心， 湖南 常德 415000）

0 引言

企业制造核心JSP 问题 （Job-Shop Scheduling Problem 作业车间调度）需要人员、物料、设备等多种资源优化整合，涉及到各类生产要素，具有数据量大、种类繁多的特点，同时加工任务也具备多品种、多批量、多工序、多任务等特征， 如何有效提高资源的利用率， 缩短加工周期、合理规划工件各工序的加工流程一直是研究的热点。

JSP 问题是NP 难问题，为了改进调度性能，一些学者进行了研究，提出了很多解决方案，得到了很多有意义的结论： 程八一采用作业分类策略产生候选表和轮换法对信息素更新提高算法效率[1]。 宋存利提出采用基于工序的随机键编码的一种混合微粒群算法HPSO 有效改进大多数经典调度问题[2]。 蒋南云等建立了双层生产计划与调度集成优化随机期望值模型[3]。 徐本柱设计了同工件同批工序间、不同工序间的并行调度算法，使分批具有方向性和预测搜索空间[4]。 Xiao-long Zheng，Ling Wang 提出了基于知识的果蝇优化算法KGFOA[5]，对于并行调度JSP 问题都有一定积极改进意义。

本文针对并行任务JSP 问题进行了更深一步的探究，结合JSP 问题的实际应用多样性和复合型，设计优化的底层染色体结构，嵌入可行解检测判断，生成动态生产调度表，混合遗传算法求解，得到更高效的并行调度JSP 问题求解方案。

1 作业车间调度数学模型

（同一台机器上，Oij在Opq之前加工）

约束条件（1）和（2）分别表达对应满足条件，其中基本符号说明：Cik—工序Oij在第K 台机器上加工完成时间；……