面向生产-库存-配送的联合调度问题及蚁群优化算法

Ant Colony Optimization for Joint Scheduling of Production, Inventory and Distribution

研究一类差异分批制造模式下的生产-库存-配送三阶段联合调度问题。在生产过程中,作业的体积有差异,而加工设备为容量限定的批处理设备,批的加工不可抢占;作业加工完毕后转入产成品库存;在配送阶段,制造企业委托第三方物流企业进行配送,车辆具有相同的运输能力;优化目标为制造企业的生产-库存-配送总成本。采用整数规划方法,对联合调度问题进行建模,证明了总成本的最小化问题为强NP-hard问题,并给出最优解的下界;设计一种改进蚁群算法进行求解,采用作业分类的策略产生候选表,有效降低算法运行时间,并采用轮换方法对信息素进行更新,避免算法陷入局部最优;设计48类算例进行仿真,对算法性能进行全面的分析验证,仿真结果表明了算法的有效性。

A three-stage joint scheduling problem for manufacturers with batch-processing machines and arbitrary-size jobs is considered. The objective is to minimize total cost for production, inventory and distribution. In the production part, jobs have arbitrary sizes and are processed in batches on machines as long as the total size of jobs in a batch does not exceed the machine capacity. The processing of a batch cannot be interrupted until all the jobs in the batch are completed. Completed jobs are put in inventory before distribution. In the distribution part, products are delivered with identical vehicles of third-party logistics company. The model of the problem is presented using integer programming and it is shown to be NP-hard. A lower bound of optimal cost is derived. Designing an improved ant colony optimization method is proposed to minimize total cost. The candidate list is generated by classification of jobs to reduce the running time. In order to avoid local optimum, the pheromone is updated with a rotation scheme. The performance of the algorithm is tested by experiments where 48 levels of instances are developed and the results show the effectiveness of the proposed algorithm.