调整时间与工序顺序相关的Job Shop调度优化方法研究

以多目标多约束Job Shop调度问题为背景，考虑工序调整、作业相似性等特点，利用成组技术和人工智能树，提出了与工序排序有关的调整时间描述方法及其调度规则，给出了此问题的混合整数规划模型，并构造了基于生物免疫机理的调度算法以提高求解此类问题的效果。介绍了保证抗体的多样性和有效性的基于自然数的抗体编码方法和基于抗体浓度的抗体激增和抑制策略。用毛纺后整理车间的一个调度实例和La31案例证明了免疫算法用于求解复杂生产调度问题的速度和效果。

Study on Optimization Method for Job Shop Scheduling with Sequence-dependent Setup

A Job Shop scheduling problem with multi-objectives and multi-constraints was studied, while the setup time of sequence and similarity of jobs were considered.The describing method and scheduling rules of sequence-dependent setup time were proposed by using group technology and artificial intelligence tree. A mixed integer programming model of the problem was presented, along with a scheduling algorithm based on biologic immunity mechanism was constructed to improve effectness of solving the problem. The array of natural number was used to form the antibody to ensure the diversity and validity of the antibody. And the proliferation and suppress strategy based on the deepness of antibody was introduced. Finally, the rapidity and results of immune algorithm in solving the problem is testified by an illustration in the collating shop of wool spinning industry and instance La31.