具有多种产品类型的最小订单提前 /拖期问题(英文)

Minimizing Earliness-Tardiness Penalties of Orders with Multi-Product Classes

针对单机多产品多订单有序独立机器调整时间的订单排产问题 ,建立了以最小化订单的提前和拖期罚值总和为优化目标的混合整数规划模型 ,分析了问题的NP -hard性和最优排序中临近批组的优化特性 ,提出一个基于过滤束搜索的拟多项式时间算法 ,算法复杂性分析和仿真结果验证了算法的有效性 .

This paper deals with the order planning of single machine with multi product classes and sequence independent setup times, and proposes a mixed integer programming model to minimize the sum of earliness/tardiness penalties of orders. It presents a pseudo polynomial algorithm based on the filtered beam search by discussing the NP hardness and the necessary condition of adjacent groups in an optimal sequence. The computational complexity analysis and simulation results have confirmed the effectiveness of the algorithm.