考虑非确定加工时间的柔性作业车间调度问题研究

Research on flexible Job-Shop scheduling problem considering uncertain processing time

加工时间不确定的柔性作业车间调度问题已逐渐成为生产调度研究的热点。采用区间表示加工时间范围,利用时间Petri网建立区间柔性作业车间调度问题形式化模型,并运用网模型的状态类图进行可达性分析,计算出所有可行变迁触发序列。通过对触发序列的时序分析,提出一种有效的逆向分步法来构造触发序列的时间约束不等式,进而求解线性规划问题来获得最小完工时间下界(上界)的优化调度策略。最后利用实例分析验证了模型及所提方法的正确性和可行性,为实际的区间柔性作业车间调度问题提供有效方案。

Flexible Job-Shop scheduling problem with uncertain processing time has gradually become a new research hotspot in production scheduling.This paper used time Petri net to model interval flexible Job-Shop scheduling problem,then it carried out the reachability analysis based on the state class graph generated by the net model,and calculated all feasible fired sequences.After the timing analysis of these fired sequences,this paper proposed a reverse step method to obtain optimal scheduling strategy for lower(upper)bound of minimum makespan by solving the linear programming problem.Finally,it gave an example to demonstrate the correctness and feasibility of the proposed method.The proposed method can provide an effective solution for the actual interval flexible Job-Shop scheduling problem.