This paper considers the single-machine single-subcontractor scheduling and outsourcing integrated optimization problem,where the objective is to minimize the weighted sum of the total completion time and total outsourcing cost,while the total outsourcing cost is subject to an upper limit.An improved removal heuristic (IRH) algorithm is developed to solve this problem.In this algorithm,the set of initial outsourcing jobs is obtained by solving new auxiliary problem with the dynamic programming technique,and specific jobs are removed from the initial outsourcing job set by introducing a judgement condition in advance.In view of the upper limit on the total outsourcing cost,there is a novel heuristic filtering sequence clan to determine the removed jobs in current outsourcing job set one by one.In simulation experiments,by generating plenty of test instances,the performance of IRH and two reported heuristics in solution quality and computational times is compared.As demonstrated in the results,IRH significantly outperforms two reported heuristics in terms of overall solution quality,and it is capable of solving test instance with up to 1500 jobs within 5.6 seconds.%针对以总完工时间与总外包费用加权和为优化目标、总外包费用不超过给定上限的单机单转包商调度与外包联合优化问题,设计出一种改进的剔除型启发式算法.该算法通过运用动态规划技术求解新的辅助问题来获取初始外包工件集,并引入判定条件提前从初始外包工件集中剔除特定工件.为满足对总外包费用的上限约束,还利用新型的启发式筛选次序族逐一确定从当前外包工件集中剔除的工件.在仿真实验中,通过生成大量的测试算例,对比分析了改进算法与另2种已报道算法在求解质量、计算时间上的表现情况.实验结果表明所提出的改进算法在解的整体质量上具备显著的比较优势,并且能在5.6秒内完成对工件总数为1500的测试算例的求解.
展开▼
