具有指数和位置学习效应的机器排序问题

运筹与管理 ›› 2011, Vol. 20 ›› Issue (2): 97-101.

具有指数和位置学习效应的机器排序问题

张新功^1,3, 严广乐¹, 唐国春², 唐海波¹

1.上海理工大学管理学院上海 200093;
2.上海第二工业大学管理工程研究所,上海 201209;
3.重庆师范大学数学学院,重庆 400047

收稿日期:2009-11-07 出版日期:2011-04-25
作者简介:张新功(1979-),男,河南项城人,博士研究生,研究方向:组合优化,排序理论。
基金资助:
上海市重点学科(S30504),中港联合科研基金(20710015),上海市研究生教育创新计划资助(JWCXSL1001)

Some Scheduling Problems With Exponential Time-dependent and Position-based Learning Effect

ZHANG Xin-gong¹, YAN Guang-le¹, TANG Guo-chun², TANG Hai-bo¹

1. Business School, University of Shanghai for Science and Technology, Shanghai 200093, China;
2. Management Engineer Institute, Shanghai Second polytechnic University, Shanghai 201209, China;
3. College of Mathematics Science, Chongqing Normal University, Chongqing 400047, China

Received:2009-11-07 Online:2011-04-25

摘要/Abstract

摘要： 本文考虑指数学习效应和位置学习效应同时发生的新的排序模型。工件的实际加工时间不仅依赖于已经加工过工件正常加工时间之和的指数函数,而且依赖于该工件所在的位置。单机排序情形下,对于最大完工时间和总完工时间最小化问题给出多项式时间算法。此外某些特殊情况下,总权完工时间和最大延迟最小化问题也给出了多项时间算法。流水机排序情形,对最大完工时间和总完工时间最小化问题在某些特殊情形下给出多项时间算法。

关键词: 排序, 单机排序, 流水机排序, 学习效应

Abstract: In this paper, we introduce a new scheduling model in which both exponential time-dependent learning effect and position-based learning effect exist simultaneously. The actual processing time of a job depends not only on an exponent function of the total normal processing time of the already processed jobs but also on its scheduled position. For the single-machine case, we derive polynomial-time optimal solutions for the problems to minimize makespan and the total completion time. In addition, we also show that the total weighted completion time problem and the maximum lateness problem can be solved in polynomial time under certain conditions. For the case of m-machine permutation flowshop, we present polynomial-time optimal for some special cases of the problems to minimize makespan and the total completion time.

Key words: scheduling, single-machine, flowshop, learning effect

中图分类号:

O223

张新功, 严广乐, 唐国春, 唐海波. 具有指数和位置学习效应的机器排序问题[J]. 运筹与管理, 2011, 20(2): 97-101.

ZHANG Xin-gong, YAN Guang-le, TANG Guo-chun, TANG Hai-bo. Some Scheduling Problems With Exponential Time-dependent and Position-based Learning Effect[J]. Operations Research and Management Science, 2011, 20(2): 97-101.

参考文献

[1] Pinedo M. Scheduling: theory, algorithms and systems[M]. 3nd, Prentice Hall, Englewood Cliffs, NJ. 2008.
[2] Biskup D. Single-machines scheduling with learning considerations[J]. European Journal of Operational Research, 1999, 115: 173-178.
[3] Mosheiov G. Scheduling problems with a learning effect[J]. European Journal of Operational Research, 2001, 132: 687-693.
[4] Cheng T C E, Wang G. Single machine scheduling with learning effect consideration[J]. Annals of Operation Research, 2000, 98: 273-290.
[5] Bachman A, Janiak A. Scheduling jobs with position-dependent processing times[J]. Journal of the Operational Research Society, 2004, 55: 257-264.
[6] Wang J B. A note on scheduling problems with learning effects and deteriorating jobs[J]. International Journal of Systems Science, 2006, 37: 827-833.
[7] Wang J B. Single-machine scheduling problems with the effects of learning and deterioration[J]. Omega, 2007, 35: 397-402.
[8] Kuo W H, Yang D L. Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect[J]. European Journal of Operational Research, 2006, 174(2): 1184-1190.
[9] Koulamas C, Kyparisis G. Single-machine and two-machine flowshop scheduling with general learning function[J]. European Journal of Operational Research, 2007, 178: 402-407.
[10] 张新功,李文华.具有学习与退化效应的单机排序问题[J].河南科学,2008,4:398-400.
[11] 秦仁杰,闻振卫.加工时间依赖资源的流水作业资源分配问题[J].运筹与管理,2005,4:67-69.
[12] Mosheiov G, Sidney J. Scheduling with general job-dependent learning curves[J]. European Journal of Operational Research, 2003, 147(3): 665-670.
[13] Graham R L, Lawler E L, Lenstra J K, Rinnooy A H G. Optimization and approximation in deterministic sequencing and scheduling: a survey[J]. Annals of Discrete Mathematics, 1979, 5: 287-326.
[14] Biskup D. A state-of-the-art review on scheduling effects[J]. European Journal of Operational Research, 2008, 188: 315-329.

[1]	金苗苗, 吴蒙洁, 罗文昌. 具有不可用区间且工件可拒绝下的单机重新排序问题的近似方案[J]. 运筹与管理, 2021, 30(8): 87-92.
[2]	刘春来, 王建军. 具有老化效应的单机共同工期安排和工件可拒绝排序问题[J]. 运筹与管理, 2021, 30(7): 66-70.
[3]	王磊, 柏庆国, 任建峰. 具有两种运输方式选择的物流排序问题[J]. 运筹与管理, 2021, 30(6): 1-5.
[4]	易平涛, 董乾坤, 李伟伟. 残缺数据下动态随机算法及应用[J]. 运筹与管理, 2021, 30(6): 6-11.
[5]	李勇军, 蔡华权. 基于Shephard距离函数的DEA TOPSIS方法研究[J]. 运筹与管理, 2021, 30(5): 116-121.
[6]	陶玲玲, 尤天慧. 基于在线评价且考虑消费者类型的酒店排序方法[J]. 运筹与管理, 2021, 30(5): 122-128.
[7]	朱运霞, 昂胜, 杨锋. 基于SMAA和公共权重的决策单元效率评价与排序[J]. 运筹与管理, 2021, 30(4): 184-189.
[8]	董君, 叶春明. 具有学习效应的半导体晶圆制造绿色车间调度问题研究[J]. 运筹与管理, 2021, 30(4): 217-223.
[9]	周丽, 杨江龙. 基于遗传算法的多通道密集式移动货架订单拣选研究[J]. 运筹与管理, 2021, 30(2): 84-90.
[10]	杨兴雨, 林虹, 何锦安, 张永. 基于排序预测的带交易费用在线投资组合策略[J]. 运筹与管理, 2021, 30(2): 168-175.
[11]	郑斐峰, 宋沁睿, 徐寅峰, 刘明. 考虑加工速率相互干扰的平行机调度最优策略研究[J]. 运筹与管理, 2021, 30(12): 1-5.
[12]	陶希闻, 江文奇. 面向直觉模糊集排序能力提升的记分函数设计研究[J]. 运筹与管理, 2021, 30(11): 34-39.
[13]	朱佳玮, 王尔大, 孙文章. 基于蒙特卡洛模拟的滨海旅游环境承载力影响因素重要性排序研究——以大连滨海景区为例[J]. 运筹与管理, 2021, 30(10): 47-52.
[14]	董晓芳, 张良勇. 产品可靠寿命的最优排序集挑选设计[J]. 运筹与管理, 2021, 30(10): 53-56.
[15]	张琳彦, 陈鸣, 徐倩, 张健. 考虑非期望因素的决策单元排序:两阶段综合效率法[J]. 运筹与管理, 2021, 30(10): 57-63.