Abstract: With the rapid development of economic globalization and information technology, outsourcing business is playing an increasingly important role in the manufacturing industry. Through outsourcing, manufacturers can not only reduce production costs and improve production efficiency, but also reduce market risks and flexibly respond to customer needs.In addition, manufacturers can concentrate their limited material and financial resources on core businesses, improving their competitiveness. Meanwhile, for subcontractors, they can effectively promote the rapid development of the manufacturing industry while providing production cooperation for manufacturers to gain profits. Therefore, both manufacturers and subcontractors can benefit from outsourcing. In actual work scenarios, manufacturers need to simultaneously make outsourcing decisions and determine production scheduling of jobs to ensure maximum benefits for all parties involved. Thus, research on scheduling and outsourcing decision-making is very meaningful and necessary.
This paper studies models on joint decisions of outsourcing and detailed jobs scheduling. In the models, a manufacturer receives a set of jobs from its customers at the beginning. Each job can be either processed by two open-shop machines in-house or outsourced to a subcontractor with a single machine. The manufacturer needs to determine which jobs or operations should be produced in-house and should be outsourced to the subcontractor. Furthermore, it needs to determine a production schedule for all jobs. The objective is to minimize the makespan of all jobs.
In this paper, two models are studied. In the model one, the first stage operation of any job is allowed to be outsourced and must be carried back to the manufacturer in batches at a certain time from the subcontractor after completion, for the second stage of processing in-house. Different from the model one, in the model two, once any job is determined to beoutsourced, both its operations must be subcontracted to the subcontractor for processing at a certain cost. The outsourced jobs at the subcontractor don't need to be transported back to the manufacturer after completion and are directly taken back by customers.Therefore, there is no transportation cost or time incurred in this model.
For the model one, an approximate algorithm is designed by using dynamic programming algorithm and open shopschedule rule. Forthe model two, two auxiliary problems are firstly constructed and solved by different dynamic programming. Then two approximation algorithmsare provided by using auxiliary problem solutions. Finally, the worst-case performance analysis for the above three algorithms is analyzed by using schedule theory and the performance ratios of all the algorithms do not exceed the model two. Furthermore,numerical examples for the three algorithms are also provided.
In the future research work, asymptotic properties of the above three approximation algorithms could be analyzed or new approximation algorithms with smaller performance ratios could be considered. In addition, the open-shop schedule problem with outsourcing costs in the objective function or the corresponding problem with more than 2 machines is worth further studying.
Finally, the authors greatly appreciate the reviewers' comments.

Key words: scheduling, outsourcing, approximation algorithm, open shop

摘要： 随着经济全球化和信息技术的高速发展,转包(外包)业务在制造业领域扮演着越来越重要的角色。通过转包,制造商不仅可以降低生产成本,提高生产效能,还可以降低市场风险,灵活应对客户需求,而转包商在为制造商提供生产合作、实现自身社会价值的同时,有效促进制造业快速发展,因此研究排序与转包问题具有非常重要的现实意义。本文研究工件排序与转包相联的决策模型,在该模型中,制造商从客户处接受一批工件,这些工件不仅可以由制造商机器加工,还可以被转包给承包商的单机加工。制造商需要确定被转包加工的工件集及所有工件的加工顺序,以极小化工件最大完工时间。本文研究制造商为两机自由作业加工环境,根据工件转包一和两个操作分别研究两个模型,基于动态规划算法和排序理论,设计三个近似算法,分析算法的性能比,并用实例进行验证。

关键词: 排序, 转包, 近似算法, 自由作业