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

Deterministic Heuristics for an Integrated Optimization Problem with Job Outsourcing Options and Single-machine Batch Scheduling

作　　者：刘乐 唐文娜 LIU Le;TANG Wenna(Business School,University of Jinan,Jinan,Shandong 250002,China;School of Automation,Qingdao University,Qingdao,Shandong 266071,China)

机构地区：[1]济南大学商学院,山东济南250002 [2]青岛大学自动化学院,山东青岛266071

出　　处：《工业工程与管理》2024年第2期140-150,共11页Industrial Engineering and Management

基　　金：国家自然科学基金资助项目(71501083);山东省自然科学基金资助项目(ZR2020MG007);中国博士后科学基金面上资助项目(2019M662296);青岛市博士后应用研究项目(2019023);济南大学社科类校级项目(19YB03)。

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

关 键 词：外包 调度 批处理机 确定型启发式算法 

分 类 号：F406.2[经济管理—产业经济]