Abstract: For the parallel machine scheduling problem of minimizing the maximum completion time, an Improved Discrete Artificial Bee Colony algorithm (IDABC) was proposed by considering the processing efficiency of the machine and the delivery time of the product as well as introducing the mathematical model of the problem. Firstly, a uniformly distributed population and a generation strategy of the parameters to be optimized were achieved by adopting the population initialization strategy, resulting in the improvement of the convergence speed of population. Secondly, the mutation operator in the differential evolution algorithm and the idea of simulated annealing algorithm were used to improve the local search strategy for the employed bee and the following bee, and the scout bee was improved by using the high-quality information of the optimal solution, resulting in the increasement of the population diversity and the avoidance of trapping into the local optimum. Finally, the proposed algorithm was applied in the parallel machine scheduling problem to analyze the performance and parameters of the algorithm. The experimental results on 15 examples show that compared with the Hybrid Discrete Artificial Bee Colony algorithm (HDABC), IDABC has the accuracy and stability improved by 4.1% and 26.9% respectively, and has better convergence, which indicates that IDABC can effectively solve the parallel machine scheduling problem in the actual scene.

Key words: parallel machine scheduling, minimization of maximum completion time, mutation operator, Artificial Bee Colony algorithm (ABC), optimization

摘要： 针对一类最小化最大完工时间的同类机调度问题，考虑到机器的加工效率和产品的交付时间，引入同类机调度问题的数学模型，提出一种改进的离散型人工蜂群算法（IDABC）求解该问题。首先，引入种群初始化策略，得到均匀分布的种群，并获得待优参数的生成策略，加快种群的收敛；其次，借鉴差分进化算法的变异算子和模拟退火算法的思想，改进雇佣蜂和跟随蜂的局部搜索策略，并利用最优解的优质信息改进侦察蜂，增加种群多样性、防止算法陷入局部最优；最后，分析算法的性能和参数，并将改进的算法应用于同类机调度问题，在15个算例上的实验结果表明，与混合离散人工蜂群（HDABC）算法相比，IDABC的求解精度和稳定性分别平均提高了4.1%和26.9%，且具有更好的收敛性，表明在实际场景中IDABC可以有效求解同类机调度问题。

关键词: 同类机调度, 最小化最大完工时间, 变异算子, 人工蜂群算法, 优化