可重用资源约束调度问题的分支定界算法研究

Branch and Bound Algorithm for Renewable Scheduling Problem

研究可重用空箱资源约束下的入厂物流车辆运输调度问题。目标函数是最小化最大完工时间。首先对该问题进行了数学描述,并建立混合整数规划模型。鉴于问题的NP难解性,提出了分支定界算法来获得最优解,并通过数值实验验证算法的有效性。

This paper is motivated by a real world scheduling problem from inbound logistics in assembly plant. A renewable resource constrained parallel machine scheduling problem is studied. An integer linear program is developed with the objective of minimizing the makespan. Based on the model, the branch and bound algorithm is developed to obtain optimal solutions. Numerical experiments are given to verify the effectiveness of proposed algorithm.