求解流水车间订单接受与调度问题的多线程并行迭代贪婪算法

针对流水车间实际生产过程中交货期短和生产能力不足的困难,研究了流水车间订单接受与调度问题,并以企业生产总净利润最大化为目标建立了数学优化模型。鉴于传统迭代贪婪算法求解流水车间调度问题的优势与不足之处,提出了一种多线程并行迭代贪婪算法(MPIG)。在算法的初始化阶段以及破坏重构阶段分别设计基于NEH(Nawaz-Enscore-Ham)的初始解产生方法以及融合不同破坏优先级的破坏方式。为提高算法搜索效率,提出了一种多线程并行搜索策略。首先利用二分查找算法快速找到订单在待插入序列中的拒绝点,随后通过多个线程同时搜索订单在序列中的局部最优位置,并最终找到订单最佳插入位置。实验结果表明,与解决类似生产调度问题的相关智能优化算法相比,所提出的MPIG具有更好的求解质量以及求解稳定性。同时,与实际生产过程中常用的启发式调度方法相比,所提出的算法在目标值上表现出不低于11%的改进率,可以有效增加企业生产总净利润,减小拖期成本。

A Hybrid Estimation of Distribution Algorithm for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times

A hybrid estimation of distribution algorithm (EDA) with iterated greedy (IG) search (EDA-IG) is proposed for solving the unrelated parallel machine scheduling problem with sequence-dependent setup times (UPMSP-SDST). For makespan criterion, some properties about neighborhood search operators to avoid invalid search are derived. A probability model based on neighbor relations of jobs is built in the EDA-based exploration phase to generate new solutions by sampling the promising search region. Two types of deconstruction and reconstruction as well as an IG search are designed in the IG-based exploitation phase. Computational complexity of the algorithm is analyzed, and the effect of parameters is investigated by using the Taguchi method of design-of-experiment. Numerical tests on 1640 benchmark instances are carried out. The results and comparisons demonstrate the effectiveness of the EDA-IG. Especially, the bestknown solutions of 531 instances are updated. In addition, the effectiveness of the properties is also demonstrated by numerical comparisons. © 2014 Chinese Association of Automation.

带状方程组并行列处理法贪心方法

利用列处理法贪心方法和分治策略,给出了一种求解任意相容性带状方程组的解或任意不相容性带状方程组最小二乘解的消息传递多指令流多数据流并行迭代解法,分析了解法的收敛性、计算复杂性和数值稳定性。该方法能使得各处理机上的负载基本平衡,得到了理想的加速比和并行效率。

带状方程组q叉树MIMD算法

利用行处理法贪心方法和分治策略给出一个基于分布式存储MIMD一级q叉树树机模型求解任意带状方程组的并行迭代算法,证明算法对相容性带状方程组收敛并分析算法的通信复杂度.

求解一类无关并行机调度的遗传迭代贪心算法

以最小化最大完工时间为优化目标,建立带工单加工约束和序相关设置时间无关并行机调度问题的混合整数规划模型;考虑现实生产对求解算法在质量、收敛速度和鲁棒性等方面的较高要求,构建一种混合遗传−迭代贪心算法。在遗传变异操作中嵌入一种迭代贪心策略的破坏和构建机制,用于提高算法的种群多样性;引入基于破坏与构建操作设计而成的快速局部搜索算法来增强算法的局部开发能力;基于实际生产数据的相关特征随机生成了一系列计算案例,并通过实验说明所提新型混合算法相较于传统混合算法的优越性。