带准备时间的单机指数时间学习效应排序问题

doi:10.12005/orms.2017.0262

运筹与管理 ›› 2017, Vol. 26 ›› Issue (11): 70-76.DOI: 10.12005/orms.2017.0262

带准备时间的单机指数时间学习效应排序问题

闫萍¹, 王吉波^1,2, 赵礼强¹

1.沈阳航空航天大学经济与管理学院,辽宁沈阳 110136;
2 沈阳航空航天大学理学院,辽宁沈阳 110136;

收稿日期:2016-04-12 出版日期:2017-11-25
作者简介:闫萍(1980-),女,辽宁沈阳人,博士,讲师,主要从事优化调度研究;王吉波(1975-),王吉波,男,辽宁沈阳人,博士,教授,大连理工大学博士生导师(兼职),主要从事生产计划与排序的研究;赵礼强(1975-),男,甘肃会宁人,博士,教授,主要从事电子商务环境下物流与供应链建模的研究。
基金资助:
辽宁省教育厅人文社会科学研究项目(W2015316);辽宁省社会科学规划基金项目(L16DGL007);辽宁省博士启动基金项目(20170520175);国家自然科学基金委员会与中国民用航空局联合资助项目(U1433124);国家自然科学基金资助项目(71471120)

Single-machine Exponentially Time-dependent Learning Effect Scheduling Problem with Release Time

YAN Ping¹, WANG Ji-bo^1,2, ZHAO Li-qiang¹

1.School of Economics and Management, Shenyang Aerospace University, Shenyang 110136, China;
2.School of Science, Shenyang Aerospace University, Shenyang 110136, China;

Received:2016-04-12 Online:2017-11-25

摘要/Abstract

摘要： 研究带有准备时间的单机学习效应模型,其中工件加工时间具有指数时间学习效应,即工件的实际加工时间是已经排好的工件加工时间的指数函数。学习效应模型考虑工件的实际加工时间同时依赖于工件本身的加工时间和已加工工件的累计加工时间,目标函数为最小化总完工时间。这个问题是NP-难的,提出了一个数学规划模型来求解该问题的最优解。通过分析几个优势性质和下界,提出分支定界算法来求解此问题,并设计启发式算法改进分支定界算法的上界值。通过仿真实验验证了分支定界算法在求解质量和时间方面的有效性。

关键词: 排序, 指数时间学习效应, 准备时间, 分支定界算法

Abstract: A single-machine scheduling problem with exponentially time-dependent learning effect and release time is studied in this paper. The exponentially time-dependent learning effect means that the actual processing time of a job is an exponential function of processing times of jobs already processed. We assume that the actual processing time of a job depends on both the job’s normal processing time and the cumulative normal processing times of all jobs already processed and consider the minimization of the total completion time as the objective function. This problem is NP-hard, and a mathematical programming model and a branch-and-bound algorithm combining with some dominance properties and lower bounds are presented to derive the optimal solution for the problem. A heuristic algorithm is also proposed to improve the upper bounds of the branch-and-bound algorithm. Computational experiments are presented to verify the performance of the branch-and-bound algorithm in terms of solution quality and time.

Key words: scheduling, exponentially time-dependent learning effect, release time, branch-and-bound algorithm

中图分类号:

O223
C934

闫萍, 王吉波, 赵礼强. 带准备时间的单机指数时间学习效应排序问题[J]. 运筹与管理, 2017, 26(11): 70-76.

YAN Ping, WANG Ji-bo, ZHAO Li-qiang. Single-machine Exponentially Time-dependent Learning Effect Scheduling Problem with Release Time[J]. Operations Research and Management Science, 2017, 26(11): 70-76.

参考文献

[1] Biskup D. Single-machine scheduling with learning considerations[J]. European Journal of Operational Research, 1999, 115(1): 173-178.
[2] 杨明明,张淑娟,韩翔凌.具有学习效应的间歇批生产的单机排序问题[J].重庆师范大学学报(自然科学版),2011,28(3):4-9.
[3] Lee W C. A note on single-machine scheduling with general learning effect and past-sequence-dependent setup time[J]. Computers and Mathematics with Applications, 2011, 62: 2095-2100.
[4] Wang J B, Hsu C J, Yang D L. Single-machine scheduling with effects of exponential learning and general deterioration[J]. Applied Mathematical Modelling, 2013, 37: 2293-2299.
[5] Wang X Y, Wang J J. Scheduling problems with past-sequence-dependent setup times and general effects of deterioration and learning[J]. Applied Mathematical Modelling, 2013, 37: 4905- 4914.
[6] 王吉波,刘璐.带准备时间的任务单机学习效应排序问题[J].大连理工大学学报,2013,53(6):930-936.
[7] Luo K. A scheduling model with a more general function of learning effects[J]. Computers & Industrial Engineering, 2015, 82: 159-166.
[8] Cheng M, Tadikamalla P R, Shang J, Zhang B. Single machine scheduling problems with exponentially time-dependent learning effects[J]. Journal of Manufacturing Systems, 2015, 34: 60- 65.
[9] Qin H, Zhang Z H, Bai D Y. Permutation flowshop group scheduling with position-based learning effect[J]. Computers & Industrial Engineering, 2016, 92: 1-15.
[10] Wu C C, Wu W H, Hsu P H, Lai K. A two-machine flowshop scheduling problem with a truncated sum of processing-times-based learning function[J]. Applied Mathematical Modelling, 2012, 36: 5001-5014.
[11] Chung Y H, Tong L I. Bi-criteria minimization for the permutation flowshop scheduling problem with machine-based learning effects[J]. Computers & Industrial Engineering, 2012, 63: 302-312.
[12] Biskup D. A state-of the-art review on scheduling effects[J]. European Journal of Operational Research, 2008, 188: 315-329.
[13] 赵传立.具有学习效应的排序问题的某些新进展[J].沈阳师范大学学报(自然科学版),2014,32(4):453- 460.

[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(2): 84-90.
[9]	杨兴雨, 林虹, 何锦安, 张永. 基于排序预测的带交易费用在线投资组合策略[J]. 运筹与管理, 2021, 30(2): 168-175.
[10]	郑斐峰, 宋沁睿, 徐寅峰, 刘明. 考虑加工速率相互干扰的平行机调度最优策略研究[J]. 运筹与管理, 2021, 30(12): 1-5.
[11]	陶希闻, 江文奇. 面向直觉模糊集排序能力提升的记分函数设计研究[J]. 运筹与管理, 2021, 30(11): 34-39.
[12]	朱佳玮, 王尔大, 孙文章. 基于蒙特卡洛模拟的滨海旅游环境承载力影响因素重要性排序研究——以大连滨海景区为例[J]. 运筹与管理, 2021, 30(10): 47-52.
[13]	董晓芳, 张良勇. 产品可靠寿命的最优排序集挑选设计[J]. 运筹与管理, 2021, 30(10): 53-56.
[14]	张琳彦, 陈鸣, 徐倩, 张健. 考虑非期望因素的决策单元排序:两阶段综合效率法[J]. 运筹与管理, 2021, 30(10): 57-63.
[15]	董晓芳, 张良勇. 排序集抽样下指数分布的产品可靠度研究[J]. 运筹与管理, 2020, 29(7): 99-104.

带准备时间的单机指数时间学习效应排序问题

Single-machine Exponentially Time-dependent Learning Effect Scheduling Problem with Release Time

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics