基于优先规则的复杂并行机调度问题研究

研究一类从实际指挥控制系统提炼的具有工件释放时间、机器可用时间和机器适用限制等约束的并行同速机调度问题.首先针对该问题建立混合整数规划模型;其次考虑到该问题的NPhard性以及实时调度的要求,提出基于优先规则的调度算法框架从而可以快速获得可行解;最后将该算法框架应用到实际案例并分析比较不同优先规则的效果,发现与工件释放时间相关的优先规则(如ERD,EFD)效果更好.值得一提的是,本文首次研究具有多重约束的并行机调度问题Pm|r_j,a_i,M_j|C_(max),TC.

Priority rule-based complex identical parallel machines scheduling

The identical parallel machine scheduling problem, which subjects to job release time, machine available time, and machine eligibility restrictions, is addressed. First, the problem is formulated as a mixed integer programming model; second, considering the problem's NP-hard characteristic and tight constraint from computational time for real scheduling, an optimization framework of priority rule-based dispatching rules is proposed; finally, the proposed framework is applied to practical instance and compared by the scheduling results, which suggest the release time related priority rules (ERD, EFD) perform better. It is worth mentioning that it is the first paper to consider the Pm|r_j, a_i, M_j|C_max, TC problem.