等待时间受限的两阶段流水车间调度问题性质研究

Investigating the Property of Two-Stage Flows Shop Scheduling Problems with Limited Waiting Time Constraints

对等待时间受限的两阶段流水车间调度问题的基本性质进行了研究。在问题的复杂性方面,证明了任何基于排列排序的调度规则都不能保证具有最优性,而且问题是强NP难的。在原问题和排列排序问题之间的关系方面,证明了满足排列排序要求的任一工件加工序列均可构成相应的可行调度;当满足一定条件时,排列排序的最优解也是原问题的最优解。这些性质为设计求解算法提供了理论基础。

Flow shop scheduling problems are a class of combinational optimization problems rooted in the engineering field.The waiting time of any jobs between two consecutive machines cannot be greater than a given value for a flow shop scheduling application.Additional restrictions arise from the high temperature and the requirement of continuity in the production environment,such as steel-making and glass manufacturing.There are only a few studies of flow shop scheduling problems with limited waiting time constraints.No comprehensive theories are available to guide the algorithm design of flow shop scheduling problems due to the lack of study on basic properties.Permutation flow shops are flow shops that maintain the same sequence of jobs throughout the entire production process.These flow shops constitute an important subclass of scheduling problems.As for the general flow shop scheduling without waiting time restrictions,there is a polynomial algorithm concerning permutation schedules for two stages.Moreover,studies on algorithms for the flow shop scheduling problem with multiple stages are mostly based on permutation schedules as well.Considering the significance of permutation flow shops,this paper studies the basic properties of the two-stage flow shop scheduling problem with limited waiting time constraints.The objective of this study is to minimize the makespan in two aspects： the complexity of problems and the relationship between the original problem and the permutation scheduling problem.For the complexity of general two-stage flow shop scheduling problems,there is a polynomial algorithm with permutation schedules presented by Johnson in 1954.Furthermore,when the machine number is less than＂4＂the optimal solutions for the permutation flow shop scheduling are the optimal ones for the original problem.However,this paper shows that the properties have fundamental changes while the limited waiting time constraints are taken into account.Johnson＇s rule is no longer an optimal algorithm for flow shop scheduling problems,even though any heuristic based scheduling on the permutation schedules cannot guarantee the optimality,and the problem with only two stages is strongly NP-hard.The relationships between the original problem and the corresponding permutation scheduling problem are discussed further.Any permutation of jobs can form feasible schedules for the original problem,and the optimal solution of the original problem can be found in permutation schedules under two kinds of conditions.We analyze the relationships among the processing times of jobs and the relationships between the upper bound of the waiting time and the processing time.These conditions are easy to satisfy in many practical production environments,especially in the production processes which are strict with each job in the waiting time between consecutive stages,or in the assembly lines with a balanced production cycle.Our analyses lead to the following conclusions.First,it is necessary to research the approximation algorithms for the two-stage flow shop scheduling problem with limited waiting time constraints.Second,heuristic approaches concerning permutation schedules can still be considered to be an effective way to address flow shop problems,although the best solution of permutation flow shop scheduling may not be an optimal schedule.Our findings provide theoretical foundations and implications for solving the two-stage flow shop scheduling problem with limited waiting time constraints.