A Branch-and-Bound Based Heuristic Algorithm for Minimizing Makespan in Machining-Assembly Flowshop Scheduling

This paper proposes a heuristic algorithm, called list-based squeezing branch and bound algorithm, for solving a machine-fixed, machining-assembly flowshop scheduling problem to minimize makespan. The machine-fixed, machining-assembly flowshop consists of some parallel two-machine flow lines at a machining stage and one robot at an assembly stage. Since an optimal schedule for this problem is not always a permutation schedule, the proposed algorithm first finds a promising permutation schedule, and then searches better non-permutation schedules near the promising permutation schedule in an enumerative manner by elaborating a branching procedure in a branch and bound algorithm. The results of numerical experiments show that the proposed algorithm can efficiently provide an optimal or a near-optimal schedule with high accuracy such as mean relative error being less than 0.2% and the maximum relative error being at most 3%.

Algorithms for Assembly Type Flowshop Scheduling Problem

An assembly type flowshop scheduling problem with minimizing makespan is considered in this paper. The problem of scheduling for minimizing makespan is first addressed, and then a new heuristic algorithm is proposed for it.

基于改进生物地理学优化算法的分布式装配置换流水车间调度问题

提出了一种改进的生物地理学优化(MBBO)算法,以最小化最大完工时间为目标,求解分布式装配置换流水车间调度问题。MBBO算法在初始化阶段利用加工时间最短(SPT)规则和NR2规则对生成的可行解进行初步优化;然后在变异阶段采用基于工厂完工时间的工件插入启发式方法调整工件的工厂分配及加工顺序;最后结合模拟退火算法,跳出局部最优解,增强算法的全局搜索能力。对900个小型实例和540个大型实例进行仿真计算,并与现有的12种启发式与元启发式算法以及基本生物地理学优化(BBO)算法进行比较,证明了MBBO算法的优越性,同时更新了70个实例的最新已知最优方案。