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

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