高级检索

    闫萍, 唐立新. 基于时间槽的并行机调度连续时间建模方法[J]. 华东理工大学学报(自然科学版), 2009, (4): 623-626.
    引用本文: 闫萍, 唐立新. 基于时间槽的并行机调度连续时间建模方法[J]. 华东理工大学学报(自然科学版), 2009, (4): 623-626.
    Slot-Based ContinuousTime Formulations for Scheduling Multiple Parallel Machines[J]. Journal of East China University of Science and Technology, 2009, (4): 623-626.
    Citation: Slot-Based ContinuousTime Formulations for Scheduling Multiple Parallel Machines[J]. Journal of East China University of Science and Technology, 2009, (4): 623-626.

    基于时间槽的并行机调度连续时间建模方法

    Slot-Based ContinuousTime Formulations for Scheduling Multiple Parallel Machines

    • 摘要: 采用基于时间槽的连续时间建模方法对匀速并行机调度问题建模以获得最优解。基于3-索引和2-索引的分配变量下标的不同定义方法,通过变换空时间槽在时间轴上的位置,分别提出了针对该并行机调度问题的不同的连续时间模型。为了进一步提高连续建模近似求解问题的效率,提出启发式算法用于减少时间槽数目。通过实验分析了所建立的不同模型的优势和缺点。实验结果表明:3-索引模型的求解速度快于2索引模型,随机安排空时间槽在时间轴上的位置能够加快模型的求解速度。此外,提出的启发式算法提高了模型的求解效率。

       

      Abstract: In this paper, a continuoustime modeling method based on timeslots is applied to the scheduling of uniform parallel machines in order to obtain optimal solutions of this problem. Based on 3-index and 2-index assignment variables and different positions of empty timeslots on time axes, a series of continuoustime formulations are presented. To improve the efficiency further, a heuristic algorithm is proposed to reduce the number of timeslots. Finally, both the superiority and disadvantage of all the formulations presented in this paper are analyzed by some experiments. The experiment results show that 3-index models are faster than 2-index ones, and the arbitrary placing of the empty timeslots on time axes can speed up the solving process of models. Moreover, the proposed heuristic algorithm can improve the solving efficiency of models to some extent.

       

    /

    返回文章
    返回