摘要
考虑了两类有一般加工时间函数的排序问题.工件的加工时间分别为基本加工时间与开工时间函数、位置函数的和.对加工时间依赖开工时间的模型,证明了一定条件下极小化最大完工时间和极小化总完工时间是多项式可解的.对加工时间依赖开工位置的模型,给出极小化最大完工时间和极小化总完工时间的最优序,同时证明了极小化加权总完工时间的一个最优排序性质并给出一个贪婪算法.
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.
出处
《运筹学学报》
CSCD
2011年第2期59-67,共9页
Operations Research Transactions
基金
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)
Social Science Planning Project of Shandong(No.10DJGJ12)
关键词
排序
单机
加工时间函数
依时间
scheduling
single machine
processing time function
time dependent
