摘要
从制造商角度出发,研究了考虑作业外包选择的单机批调度联合优化问题,建立了以最小化作业外包总成本与内部批加工总成本之和为目标函数的0-1规划模型,并分析了该问题的NP困难性和优化性质.在此基础上,利用两种不同的外包作业集决策方式以及与之相适应的作业筛选次序组,设计出两种具备多项式时间复杂度的确定型启发式算法,即作业加入型算法和作业剔除型算法.在仿真实验中,针对大量测试算例对比分析了这两种算法在优化质量、运行耗时上的性能表现.实验结果表明,两种算法均能在极短时间内求得较高质量的近似解,但作业剔除型算法在优化质量上要显著优于作业加入型算法.
Abstract
The integrated optimization problem of job outsourcing and scheduling on a single batch-processing machine was studied from the manufacturers'perspective.A 0-1 programming model was established with the objective of minimizing the sum of the total job outsourcing cost and total in-house batch processing cost,while both nondeterministic polynomial(NP)hardness and optimality properties were analyzed.Two deterministic heuristics in polynomial complexity were proposed by two different ways of determining the set of outsourcing jobs and their respective appropriate groups of job filtering orders.They were job addition heuristic(JAH)and job removal heuristic(JRH).In the simulation experiments,performance of both JAH and JRH algorithms in solution quality and running time was comparatively analyzed over plenty of problem instances.Experimental results show that the two heuristics are both capable of obtaining high-quality near solutions in a short time,and JRH indeed significantly outperforms JAH in terms of optimization quality by comparison.
基金项目
国家自然科学基金(71501083)
山东省自然科学基金(ZR2020MG007)
中国博士后科学基金面上项目(2019M662296)
青岛市博士后应用研究项目(2019023)
济南大学社科类校级项目(19YB03)
NETL
NSTL
万方数据