Meta-heuristics for unrelated parallel machines scheduling with random rework to minimize expected total weighted tardiness
Meta-heuristics for unrelated parallel machines scheduling with random rework to minimize expected total weighted tardiness
复制标题
用于不相关并行机器调度的元启发式随机返工以最小化预期总加权迟到
DOI：
10.1016/j.cie.2020.106505
复制
发表时间：
2020
影响因子：
7.9
通讯作者：
Mao Ning
中科院分区：
文献类型：
--
作者：
Wang Xiaoming;Li Zhantao;Chen Qingxin;Mao Ning
具有随机返工的无关并行机排序问题在工业上有着广泛的应用。由于该问题已被证明是强意义上的NP难问题，因此我们专注于基于确定性优化技术的高效近似方法的实现。分别建立了基于聚集任务估计和基于分离任务估计的混合整数规划模型。为了得到大规模算例的近似解，我们进一步提出了改进的遗传算法和模拟退火法。算法的初始解通过有效的优先规则得到。基于随机生成实例的计算实验表明，所提出的聚合任务估计比已有的单独任务估计更高效、更稳定。所提出的元启发式算法优于经典的优先规则，更接近于精确算法。具体而言，模拟退火法比遗传算法具有更高的计算效率。
Unrelated parallel machines scheduling problems with random rework have many industrial applications. Since the problem has been proven to be NP hard in a strong sense, we concentrate on the implementation of efficient approximate methods based on deterministic optimization techniques. Two mixed integer programming models are formulated based on aggregate and separate task estimation, respectively. In order to obtain an approximate solution of a large-scale instance, we further propose modified genetic algorithm and simulated annealing algorithm. The initial solutions of the algorithms are obtained by effective priority rules. Computational experiments based on randomly generated instances demonstrate that the proposed aggregate task estimation is more efficient and more stable than the existing separate task estimation. The proposed meta-heuristics are superior to classical priority rules and close to the exact method. Specifically, simulated annealing algorithm is preferred due to higher computational efficiency than that of genetic algorithm.