English

运筹学学报 ›› 2012, Vol. 16 ›› Issue (1): 121-128.

• 运筹学 • 上一篇    

工件可转包加工的排序问题研究

仲维亚1, 刘晓蕾1, 霍志明1   

  1. 1.  上海大学理学院数学系, 上海, 200444
  • 收稿日期:2011-09-23 修回日期:2011-11-12 出版日期:2012-03-15 发布日期:2012-03-15
  • 通讯作者: 仲维亚 E-mail:wyzhong@shu.edu.cn
  • 基金资助:

    上海市教委重点学科(S30104)资助课题

A Single Machine Scheduling Problem with Subcontracting Options

 ZHONG  Wei-Ya1, LIU  Xiao-Lei1,   Huo-Zhi-Ming1   

  1. 1. Department of Mathematics, College of Science, Shanghai University, Shanghai 200444, China
  • Received:2011-09-23 Revised:2011-11-12 Online:2012-03-15 Published:2012-03-15

PDF

1360

被引次数

4

摘要：  研究工件可以转包加工的单台机排序问题: 有n个工件, 在零时刻已经到达一个单台机处, 每个工件可以由加工者自有的单台机器加工或者转包给其他机器加工. 如果工件被转包加工, 那么其完工时间等于在自有机器上的加工时间, 而产生的加工费用与在自有机器上加工的费用不同. 假设被转包加工的工件的完工时间和加工费用与转包加工机器的总负载没有关系.目标函数是最小化工件最大完工时间与总加工费用的加权和. 该问题已经被证明是NP-难的. 最后给出该问题的伪多项式时间最优算法, 并且提出一个完全多项式时间近似方案(FPTAS).

关键词: 排序, 伪多项式时间最优算法, FPTAS

Abstract: In this paper, we study a single machine scheduling problem with subcontracting options as follows: there are n jobs which are available at time zero. Each job can be processed in house on a single machine or subcontracted to a subcontractor. If a job is subcontracted to the subcontractor, its delivery lead time is the same as the in-house processing time, but the processing cost is different from the in-house processing cost. The delivery lead time and processing cost of a subcontracted job is independent of the total workload of the subcontractor. The objective is to minimize the weighted sum of the maximal completion time (which is defined as the larger one of the maximal completion time of the in-house jobs and the maximal delivery lead time of the out-house jobs) and the total processing cost. This problem has been proved to be NP-hard. We first give a pseudo-polynomial time algorithm for this problem, then give an FPTAS.

Key words: scheduling, pseudo-polynomial time algorithm, FPTAS