多阶段连续型柔性制药车间调度

针对包含易变质药品的柔性均衡制药车间调度问题，提出一种基于列生成框架的算法.通过设计面向虚拟作业对的排序策略，表征制药过程中的无等待现象，利用动态规划方法求解由原调度问题衍生出的价格问题，并设计改进的分支定界算法求得最终的调度方案.由不同规模的数值实验可知，对于规模较小的多阶段连续型柔性制药车间调度问题，提出的算法可求得最优解；对于传统优化软件难以求解的较大规模问题，该算法仍可在较短时间内得到高质量的药品生产调度方案，从而验证了该调度算法的有效性，并可为实际连续型柔性制药车间提供辅助排程决策.
Abstract: A novel algorithm based on column generation was proposed for the flexible proportionate job shop scheduling problem with rapidly perishable medicine. The no-wait constraint in pharmaceutical process was represented with the sorting strategy based on job pairs. The pricing problem derived from the master problem was solved by dynamic programming. An improved branch and bound algorithm was designed to obtain the optimal solution. The numerical experimental results show that the algorithm can obtain the optimal solutions for the small-scale multi-stage no-wait pharmaceutical scheduling instances, and can solve the medium to large scale instances which cannot be solved by traditional optimization packages. High quality solutions can be achieved by using the proposed method within a relatively short period of time. Therefore, the effectiveness of the algorithm is verified, as well as its application values in the actual pharmaceutical production process.