带转包选项的自由作业排序

Open-shop Scheduling With Option of Outsourcing

本文研究两机自由作业排序问题,工件的两个工序既可以在制造商的两台自由作业环境机器上加工,也可以转包给两承包商加工.每承包商有一台单机,仅能加工指定的工序.工件被转包时制造商需要付出一定数量的转包费用.制造商需要同时确定转包工件集及未转包工件的加工顺序,目标是极小化转包费用与未转包工件时间表加工总长之和.本文根据转包费用系数的不同。

This paper addresses a two-machine open-shop scheduling in which jobs received from customers can be either processed at a manufacturer or outsourced to subcontractors. Each job consists of two operations which could be processed by two machines at the manufacturer＇s plant. Each subcontractor has a single machine which can only process the specified operations of jobs. Operations processed by subcontractors require paying an amount of outsourcing cost. The manufacturer needs to determine simultaneously the jobs outsourced and the schedule of the jobs in-house. The objective is to minimize the sum of outsourcing costs and the makespan of the schedule in-house. According to different outsourcing cost coefficients, we analyze the computational complexities and derive polynomial approximation and pseudo-polynomial time algorithms for the NP-hard cases.