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

Two Models of Single Machine Scheduling with General Processing Time Functions

作　　者：王成飞[1] 张玉忠[1] 苗翠霞[2] 

机构地区：[1]曲阜师范大学管理学院,山东日照276826 [2]曲阜师范大学数学科学学院,山东曲阜273165

出　　处：《运筹学学报》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)

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

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

分 类 号：Q157[生物学—普通生物学]