Heuristic Scheduling in Machining-Assembly Flowshop under Supply Chain Environment

点击翻译按钮获取中文摘要

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.