摘要
Lot scheduling problem with idle time transfer between processes to minimize mean flow time is very important because to minimize mean flow time is to minimize work in process. But the problem is NP hard and no polynomial algorithm exists to guarantee optimal solution. Based the analysis the mathematical structure of the problem, the paper presents a new heuristic algorithm. Computer simulation shows that the proposed heuristic algorithm performs well in terms of both quality of solution and execution speed.
以极小化平均流程时间为目标的批排序问题是十分重要的,因为极小化平均流程时间等价于极小化平均在制品占用.由于这一问题属于NP-难题,不存在多项式算法保证求得最优解.基于对该问题模型结构分析,本文提出了一个新的启发式算法.计算机模拟结果表明,该算法简便且优度高.