具有前成组约束的两阶段柔性流水车间的启发式算法.pdfVIP

学兔兔 第48卷第22期 机 械 工 程 学 报 V_01．48 NO．22 2012年 11月 JOURNAL OF MECHANICAL ENGINEERING NOV． 2 0 1 2 DoI：l0．3901／ E．2012．22．189 具有前成组约束的两阶段柔性流水 车间的启发式算法水 黎展滔 陈庆新 毛 宁 (广东工业大学广东省计算机集成制造系统重点实验室 广』 I1 510006) 摘要：以模具加工车间为背景，分析具有前成组约束的两阶段柔性流水车间的特点，在对前成组约束进行定义和数学描述的 基础上，以最少化最大完工时间为目标，建立具有前成组约束的、工件批量到达的两阶段柔性流水车间调度问题的数学模型， 并且在第一阶段由两个成组加工单元构成；接着针对这一模型，提出一种启发式求解算法 H ；运用数学分析的手段，给出 该算法优化结果的一个下界；设计大量的实例测试集，将启发式算法H 与其他三种改造后的经典启发式算法进行性能比较， 不仅验证启发式算法H 的有效性，而且还发现随着任务规模的增大，启发式算法H，的优越性更加明显，这一结论对H，算法 在模具加工车间调度上的应用具有重要意义。 关键词：启发式算法 柔性流水车间 前成组约束 中图分类号：F406 Heuristic Algorithms for Two—stage Flexible Flow Shop Scheduling with Head Group Constraint LI Zhantao CHEN Qingxin MAO Ning (Key Laboratory of Computer Integrated Manufacturing System of Guangdong Province， Guangdong University of Technology,Guangzhou 5 1 0006) Abstract：Based on a background to the shops in the mould manufacturers，It considers a two—stage flexible flow shop scheduling problem subject to release dates，where the first stage is made up of unrelated machines and tasks have group constraint．Based on defming two·-stage flexible flow shop with head group constraint and giving its mathematical description systematically,a mathematic model is formulated where the objective is to find a schedule that minimizes makespan．Because this problem is NP—hard， a constructive heuristic algorithm H is proposed and its lower bound(LB)is proved．In addition，some classical heuristics are developed．In order to test the efficiency of the algorithm，sets of examples are designed．Compared to the classical developed heuristics，the performance of algorithm H is m