Single Machine Scheduling with Outsourcing Under Different Fill Rates or Quantity Discount Rates

摘要

In this paper, we consider two single machine scheduling problems with outsourcing under different fill rates or quantity discount rates. From the manufacturer point of view, to maintain a predefined high service level under limited production capacity, it is required that the number of outsourced jobs must belong to a given interval [a, b]. We call this model "scheduling with outsourcing under different fill rates". Meanwhile, from the outsourcers point of view, in order to encourage more outsourcing actions from the manufacturer, the outsourcers might provide an attractive discount scheme. Here, we assume that all discount rates depend only on the quantity (number) of the outsourced jobs. That is, the actual outsourcing cost equals to the original outsourcing cost multiplied by the corresponding discount rate. This model is called "scheduling with outsourcing under different quantity discount rates". The objective is to minimize the sum of the makespan of the processed jobs and the (actual) outsourcing costs of the outsourced jobs. For the above two problems, some optimal algorithms, approximation algorithms and approximation schemes are proposed.