混合离散人工蜂群算法求解含不相关并行机的分布式柔性流水线调度

Hybrid discrete artificial bee colony algorithm for distributed flexible flowline scheduling with unrelated parallel machines

研究每阶段含不相关并行机的分布式柔性流水线调度问题.考虑顺序相关准备时间和工件动态到达时间,以最小化总加权提前/拖期惩罚为目标建立整数规划模型,提出一种融合离散差分进化算法、变邻域下降算法和局域搜索的混合离散人工蜂群算法以获取近优解.该算法采用基于工厂-工件号的编码以及基于机器最早空闲时间的动态解码机制,通过随机规则和均衡分派策略生成初始工厂-工件序列群,在引领蜂阶段引入离散差分进化算法产生优质工厂-工件序列,在跟随蜂阶段利用变邻域下降算法在被选择序列附近继续搜索以得到邻域序列,在侦察蜂阶段设计基于关键/非关键工厂间插入的局域搜索提高算法搜索能力.通过仿真实验测试不同规模的算例,实验结果表明,所提出的混合离散人工蜂群算法表现出较好的求解性能.

A distributed flexible flowline scheduling problem with unrelated parallel machines at each stage is studied.Considering sequence-dependent setup times and job dynamic arrival times, an integer programming model is established with the objective of minimizing total weighted earliness and tardiness penalty. A hybrid discrete artificial bee colony algorithm is proposed combined with the discrete differential evolution algorithm, the variable neighborhood descent algorithm and local search so as to obtain near optimal solutions. In this algorithm, factory-job number based encoding is applied and a dynamic decoding mechanism with the earliest machine idle time is designed. The initial factory-job sequence group is then generated by using a random rule and an average assignment strategy. In the leading bee phase, the discrete differential evolution algorithm is introduced to yield factory-job sequences with high quality. In the following bee phase, a variable neighborhood descent algorithm is used to search around the selected sequences in order to gain neighborhood sequences. Local search based on insertion between critical/non-critical factories is designed to enhance algorithm search ability in the scout bee phase. Simulation experiments are performed on different scale problems, and testing results demonstrate the proposed hybrid discrete artificial bee colony algorithm has a better resolution performance.