Hybrid Flow Shop Scheduling Problem With Unbalanced Workload

In the large-scale complex modern production system, how to make management decisions and organize production has become decision-makers' major concern. Shop scheduling is an important component of production scheduling. Effective production scheduling can improve the production efficiency, save production costs and provide information for planning external activities. The studies of shop scheduling are not only to guide actual production but also to extend other areas related to resource allocation. Therefore, the research of production scheduling problem has important theoretical significance as well as great practical meaning.Hybrid flow shop scheduling problem is one of the most important scheduling problems. Due to its important engineering applications, especially in manufacturing industry and assembly industry, it has been the focus of production managers and researches. The theory of constraints indicates that the unbalanced capacity of production line should be designed in order to minimize the adverse impact of stochastic fluctuation. To approach the actual production, this paper discusses hybrid flow shop with unbalance workload (HFSUW) scheduling problem. The main research work lies in two aspects as follows.The deterministic HFSUW scheduling problem. According to the feature of HFSUW, a decomposition-coordination method is used for scheduling. HFSUW is decomposed into upstream non-bottleneck stages, bottleneck stage and downstream non-bottleneck stages. Firstly, the capacity of machines in upstream non-bottleneck stages is relaxed and bottleneck stage schedule is obtained. Secondly, based on the schedule of bottleneck stage, upstream non-bottleneck stages are scheduled coordinately. Thirdly, downstream non-bottleneck stages are scheduled. The performance of schedule is measured by the relative deviation between the makespan and the lower bound. The simulation results show that when the capacity is unbalanced, both the average deviation from the lower bound and the largest deviation from the lower bound obtained by decomposition-coordination algorithm are small comparing with other algorithms.Predictable scheduling of HFSUW subject to random breakdown. The schedule obtained by decomposition-coordination method is served as initial schedule. The effect of random machine breakdown occurred on upstream non-bottleneck stage, bottleneck stage and downstream non-bottleneck stage is analyzed respectively. When the execution procedure is subject to a machine breakdown, right shift rescheduling is used to absorb the breakdown. The computational experiments reveal that the breakdown occurred on bottleneck stage has the most impact on efficiency performance. To deal with the breakdown occurred on bottleneck stage of HFSUW, predictable schedule is obtained by inserting additional idle time, which can absorb the effect of breakdown. To examine the influence of the amount and position of additional idle time inserted in predictable schedule, three inserted additional idle time methods are presented. The predictability of predictable schedule is measured by the average absolute deviation between the planned completion time and the realized completion time. Extensive simulation results show that when the breakdown occurred on the two-thirds of job sequence, predictable schedules can provide high predictability with minor sacrificed efficiency performance. Compared with the efficiency performance and the predictability of predictable schedule simultaneously, the predictable schedule obtained by inserting sequence-independent additional idle time at bottleneck stage is better than others.