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

运筹学学报 ›› 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)

摘要/Abstract

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

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

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

中图分类号:

中图分类号: Q157 数学分类号: 90B35

王成飞, 张玉忠, 苗翠霞. 两类加工时间是一般函数的单机排序问题[J]. 运筹学学报, 2011, 15(2): 59-67.

WANG Cheng-Fei, ZHANG Yu-Zhong, MIAO Cui-Xia. Two Models of Single Machine Scheduling with General Processing Time Functions[J]. Operations Research Transactions, 2011, 15(2): 59-67.

[1]	陈荣军, 刘永财, 黄河, 唐国春. 单机供应链排序问题动态规划算法[J]. 运筹学学报（中英文）, 2026, 30(1): 171-178.
[2]	孟兰梦, 马冉, 张玉忠. 在NDP约束条件下考虑带退化效应的单机在线调度[J]. 运筹学学报（中英文）, 2026, 30(1): 179-187.
[3]	吴弘一, 王冬, 万龙, 罗文昌. 嵌套加工型限制下的混合分批平行机排序问题的近似算法[J]. 运筹学学报（中英文）, 2026, 30(1): 188-196.
[4]	李大伟, 李刚刚. 考虑人员不可用及工件带退化效应的单机排序问题[J]. 运筹学学报（中英文）, 2025, 29(4): 14-26.
[5]	赵娣, 余金, 鲁习文. 单机两代理串行分批排序问题的近似算法[J]. 运筹学学报（中英文）, 2025, 29(2): 184-193.
[6]	李娜, 马冉, 李龙, 张玉忠. 具有学习效应的预制构件生产调度研究[J]. 运筹学学报（中英文）, 2025, 29(1): 19-30.
[7]	崔同欣, 夏倩, 张新功. 基于松弛工期的总加权误工单机双代理排序问题[J]. 运筹学学报（中英文）, 2025, 29(1): 31-40.
[8]	杜诗翩, 顾满占. 带机器维护的最小化总误工数期望的随机排序问题研究[J]. 运筹学学报（中英文）, 2025, 29(1): 142-158.
[9]	李文杰, 杜智慧, 苏孟龙. 加工时间与运输时间具有一致性的单机NDP约束在线排序问题研究[J]. 运筹学学报（中英文）, 2024, 28(4): 18-28.
[10]	葛晴, 录岭法, 原晋江, 张利齐. 单机上一个与总完工时间及最大完工时间相关的工件可拒绝的ND双代理排序问题[J]. 运筹学学报（中英文）, 2024, 28(4): 66-74.
[11]	焦成文. 具有线性前瞻区间的单机平行批在线排序[J]. 运筹学学报（中英文）, 2024, 28(4): 111-116.
[12]	徐娟年, 马冉, 韩雯雯, 张玉忠. 工件权重带限制的最小化最大加权完工时间的单机在线排序问题[J]. 运筹学学报（中英文）, 2024, 28(2): 71-80.
[13]	吴琼, 王长军. 基于拉格朗日松弛的产能共享讨价还价研究[J]. 运筹学学报（中英文）, 2024, 28(2): 93-102.
[14]	高洁, 邹娟, 隋玉康, 张玉忠. 带有退化维护活动和工件可拒绝的非同类机排序问题[J]. 运筹学学报, 2023, 27(3): 137-149.
[15]	龚铭炀, 谈之奕, 严羽洁. 两台同类机排序问题SPT算法的最坏情况比[J]. 运筹学学报, 2022, 26(3): 92-108.