English

运筹学学报 ›› 2011, Vol. 15 ›› Issue (2): 59-67.

• 运筹学 • 上一篇    下一篇

两类加工时间是一般函数的单机排序问题

王成飞, 张玉忠, 苗翠霞   

  • 出版日期:2011-06-15 发布日期:2011-06-15

Two Models of Single Machine Scheduling with General Processing Time Functions

WANG  Cheng-Fei, ZHANG  Yu-Zhong, MIAO  Cui-Xia   

  • Online:2011-06-15 Published:2011-06-15
  • Supported by:

    Supported by the National Natural Science Foundation of China (No. 11071142, 70971076), ``Taishan Scholar" Project in Applied Mathematics of Shandong Province, Shandong Provincial Natural Science Foundation(No. ZR2010AM034), Specialized Research Fund for the Doctoral Program of Higher Education (No. 20070446001) and Social Science Planning Project of Shandong (No. 10DJGJ12)

PDF

1301

被引次数

1

摘要： 考虑了两类有一般加工时间函数的排序问题. 工件的加工时间分别为基本加工时间与开工时间函数、位置函数的和. 对加工时间依赖开工时间的模型，证明了一定条件下极小化最大完工时间和极小化总完工时间是多项式可解的. 对加工时间依赖开工位置的模型，给出极小化最大完工时间和极小化总完工时间的最优序，同时证明了极小化加权总完工时间的一个最优排序性质并给出一个贪婪算法.

关键词: 排序, 单机, 加工时间函数, 依时间

Abstract: Two models of single machine scheduling  with general processing time functions are considered.  Job's processing time is assumed to be the sum of  basic processing time and a function of starting time or  a function of position.  For processing over starting time model, the makespan minimization problem and total completion time minimization problem are polynomially solvable under certain conditions, which have more generality compared with previous articles. For processing  over position  model, there are optimal schedules for makespan minimization problem and total completion time minimization problem.   A property of optimal schedule and a greedy algorithm for total weighted completion time minimization problem are presented.

Key words:  scheduling, single machine, processing time function, time dependent

中图分类号: