Heuristic Scheduling in Machining-Assembly Flowshop under Supply Chain Environment

研究了柔性制造单元(FMC)中以最小完工时间为目标的调度问题。柔性制造技术能够有效地加工各种零件，并小批量地装配成多种产品，以满足快速变化的生产结构和需求，因此受到了制造商的广泛关注。将FMCS建模为最小化完工时间的加工装配流水作业(MAFS)模型，并提出了两种启发式算法来有效地寻找该问题的近似最优调度。其中一种算法是启发式算法，通过将NEH算法应用于转换后的虚拟流水作业模型，找到原始MAFS模型的一些有希望的调度，然后将基于Johnson规则的策略、基于关键作业/生产线的作业移动策略应用于该调度。另一种是基于分支定界(B&B)的局部搜索算法，其通过使用分支定界算法中的分支过程以枚举方式搜索初始调度的邻域。在该算法中，首先利用有前途的启发式方法寻找初始调度，然后利用基于B&B的并行局部搜索来获得最优(或接近最优)调度。数值实验表明，所提出的算法能够有效地提供接近最优的调度，平均相对误差小于1%，最大相对误差最大为3%。将所提算法扩展到动态和多目标调度的情况将是下一步的工作之一。

This research dealt with scheduling problems to minimize makespan in a flexible manufacturing cell(FMC). FMC has attracted manufactures because it is effective for machining various component parts and assembling them into many kinds of products in a small lot to meet a rapid change in production-mix and its demand. We formulated the FMCs as machining-assembly flowshop(MAFS) models to minimize makespan and proposed two types of heuristic algorithms for finding a near optimum schedule to this problem efficiently.One of the proposed algorithms is a heuristic algorithm, in which some promising schedules for the original MAFS model are found by applying NEH algorithm to converted virtual flowshop models in various ways, and then better schedules are searched by applying some job-moving strategies, such as Johnson-rule-based strategy, critical-job/line-based strategies, to the schedules.Another one is a Branch-and-Bound(B＆B) based local search algorithms, which searches neighborhood of initial schedules in an enumerative manner by using a branching procedure in a branch-and-bound algorithm. In this algorithm, some initial schedules are found first by using promising heuristic methods, and then a B＆B-based parallel local search is implemented for obtaining an optimal(or a near-optimal) schedule.Numerical experiments were implemented to demonstrate that booth of the proposed algorithms can efficiently provide a nearoptimum schedule with high accuracy such as mean relative error being less than 1% and the maximum relative error being at most 3%.Extension of the proposed algorithms to the case of dynamic and multiobjective scheduling will be one of our future works.