一类缓冲区有限的两阶段混合流水车间调度问题及算法

    Heuristic Scheduling Method for a Class of Two-Stage Hybrid-Flow Shop with Limited Buffers

    • 摘要: 针对炼钢-连铸生产调度问题中温装模式(CCHCR),提炼出一类有缓冲区约束的两阶段混合流水车间调度问题,并利用静态和离散时间的整数规划模型对其进行描述。从一种新的角度对问题特征进行分析,将原问题转化为无等待的三阶段混合流水车间调度问题。在此基础上,提出了启发式算法JB与JBN,算法JB以启发式规则形成工件加工序列,采用递归回溯消除相邻阶段间缓冲区有限冲突,算法JBN在此基础上结合NEH插入搜索,并以最小化第一阶段机器空闲时间为目标函数进行优化,对工件序列进行调整,进一步提高解的质量。通过对实验结果的分析,分别得出了2种启发式算法的优化效果,表明算法的可行性和有效性。

       

      Abstract: The CC-HCR (continous costing hot-charge rolling) process in the steelmaking continuous casting production can be described as a kind of two-stage hybrid flow shop scheduling problem. A static and discrete-time integer programming model is established for it. By analyzing the characteristics of the problem in a new viewpoint, it turns out to be a three-stage hybrid flow shop scheduling problem with no-wait constraint. On this basis, two heuristic algorithms named JB and JBN are proposed. For the former, jobs are processed by problem-dependent heuristic rules. The backtracking is used to solve the constraints of limited buffers. For the latter, it is combined with NEH, which minimizes the idle time at the first stage as the objective function, adjusts the job sequence at the second stage, and improves the quality of the solution at the third stage. Furthermore, computational experiments are conducted to evaluate the effectiveness of these algorithms and it shows that they are feasible and effective.

       

    /

    返回文章
    返回