转包且具有不同费用时间段的排序问题

本文研究制造商可以将工件转包给承包商加工的排序模型,承包商仅有一台机器,转包费用由分配给转包工件的不同时间段费用确定.本文分别研究制造商有一台单机及两台自由作业机器环境情形,需要确定被转包工件集及全部工件的加工顺序,使得工件最大完工时间与转包费用和最小.本文利用归约方法对制造商每个机器环境,证明问题NP困难性,并提出动态规划算法.

SCHEDULING WITH OUTSOURCING AND VARIABLE TIME SLOT COSTS

This paper is concerned with scheduling model where each job can be either processed at a manufacturer or outsourced to a subcontractor which has a single machine for processing. The outsourcing cost that the subcontractor charges the manufacturer is determined by the cost of time slots allocated to the outsourced jobs. This paper considers that the manufacturer has a single machine or two open-shop machines environment. The manufacturer needs to determine simultaneously the set of outsourced jobs and the schedule of the all jobs such that the sum of the makespan of all jobs and the outsourcing cost is minimized. For each machine environment at the manufacturer, we show the problem is NP-hard by reduction method and derive a dynamic programming algorithm.