作业外包与单机批调度联合优化问题的确定型启发式算法

从制造商角度出发，研究了考虑作业外包选择的单机批调度联合优化问题，建立了以最小化作业外包总成本与内部批加工总成本之和为目标函数的0-1规划模型，并分析了该问题的NP困难性和优化性质。在此基础上，利用两种不同的外包作业集决策方式以及与之相适应的作业筛选次序组，设计出两种具备多项式时间复杂度的确定型启发式算法，即作业加入型算法和作业剔除型算法。在仿真实验中，针对大量测试算例对比分析了这两种算法在优化质量、运行耗时上的性能表现。实验结果表明，两种算法均能在极短时间内求得较高质量的近似解，但作业剔除型算法在优化质量上要显著优于作业加入型算法。