[1]徐海燕,李小平.基于学习和恶化效应模型的单机调度[J].东南大学学报(自然科学版),2013,43(6):1185-1189.[doi:10.3969/j.issn.1001-0505.2013.06.010]
 Xu Haiyan,Li Xiaoping.Single-machine scheduling based on both learning and deterioration effects[J].Journal of Southeast University (Natural Science Edition),2013,43(6):1185-1189.[doi:10.3969/j.issn.1001-0505.2013.06.010]
点击复制

基于学习和恶化效应模型的单机调度()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
43
期数:
2013年第6期
页码:
1185-1189
栏目:
计算机科学与工程
出版日期:
2013-11-20

文章信息/Info

Title:
Single-machine scheduling based on both learning and deterioration effects
作者:
徐海燕12李小平1
1东南大学计算机科学与工程学院, 南京 211189; 2金陵科技学院公共基础课部, 南京 211169
Author(s):
Xu Haiyan12 Li Xiaoping1
1School of Computer Science and Engineering, Southeast University, Nanjing 211189, China
2Department of Public Basic Course, Jinling Institute of Technology, Nanjing 211169, China
关键词:
单机调度 恶化效应 学习效应 最优化规则
Keywords:
single machine scheduling deteriorating effect learning effect optimal rule
分类号:
TP301.6
DOI:
10.3969/j.issn.1001-0505.2013.06.010
摘要:
为了提高已有模型中仅单独考虑学习和(或)恶化效应所产生处理时间的准确性,提出一个同时考虑学习和(或)恶化效应的模型.该模型将学习和恶化效应函数都建模为关于位置和累积时间的函数,因此该模型较已有模型应用更广泛.将模型应用于单机调度中,证明了当效应函数具有某些特定性质时,极小化最大完工时间、极小化总完工时间和、极小化总完工时间平方和等问题是多项式时间可解的,极小化加权总完工时间和、极小化总延误时间和、极小化最大延误时间等问题在某些条件下是多项式时间可解的.最后通过具体实例对结论进行了验证.
Abstract:
In order to improve the accuracy of processing time with only learning/deterioration effects in existing models, an integrated model with both learning effects and deterioration effects is developed. The position of the scheduled job and the total actual processing times of the processed jobs are taken into account in the proposed model, which is more practical than existing ones. The developed model is applied to several single machine scheduling problems. Problems with the make-span, the total completion time and the square sum of completion times minimization using the learning effects and deterioration effects with special properties are proved to be optimally solvable in polynomial time. As well, the total weighted completion time minimization problem, the total tardiness minimization problem, and the maximum tardiness minimization problem are proved to be optimally solvable in polynomial time only for certain assumptions. Optimal solutions are demonstrated by examples for the considered problems using the proved optimal rules.

参考文献/References:

[1] Pinedo M L. Scheduling: theory, algorithms, and systems[M]. Berlin: Springer, 2012.
[2] Biskup D. A state-of-the-art review on scheduling with learning effects[J]. European Journal of Operational Research, 2008, 188(2): 315-329.
[3] Biskup D. Single-machine scheduling with learning considerations[J]. European Journal of Operational Research, 1999, 115(1): 173-178.
[4] 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.
[5] Lee W-C, Wu C-C. Some single-machine and m-machine flowshop scheduling problems with learning considerations[J]. Information Sciences, 2009, 179(22): 3885-3892.
[6] Low C Y, Lin W-Y. Single machine group scheduling with learning effects and past-sequence-dependent setup times[J]. International Journal of Systems Science, 2012, 43(1): 1-8.
[7] Gordon V S, Potts C N, Strusevich V A, et al. Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation[J]. Journal of Scheduling, 2008, 11(5): 357-370.
[8] Yang S-J. Single-machine scheduling problems simultaneously with deterioration and learning effects under deteriorating multi-maintenance activities consideration[J]. Computers and Industrial Engineering, 2012, 62(1): 271-275.
[9] Wang J-B. Single-machine scheduling problems with the effects of learning and deterioration[J]. Omega, 2007, 35(4): 397-402.
[10] 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(4): 2293-2299.
[11] Lai P-J, Lee W-C. Single-machine scheduling with general sum-of-processing-time-based and position-based learning effects[J]. Omega, 2011, 39(5): 467-471.
[12] Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling theory: a survey [J]. Annals of Discrete Mathematics, 1979, 5(2): 287-326.

相似文献/References:

[1]朱悦,张玉林,宋旼珊.考虑手术间及医疗团队间准备时间的手术排程[J].东南大学学报(自然科学版),2015,45(6):1218.[doi:10.3969/j.issn.1001-0505.2015.06.034]
 Zhu Yue,Zhang Yulin,Song Minshan.Surgical scheduling considering setup time between surgeries and setup time between surgical teams[J].Journal of Southeast University (Natural Science Edition),2015,45(6):1218.[doi:10.3969/j.issn.1001-0505.2015.06.034]

备注/Memo

备注/Memo:
作者简介: 徐海燕(1980—),女,博士生;李小平(联系人),男,博士, 教授,博士生导师,xpli@seu.edu.cn.
基金项目: 国家自然科学基金资助项目(61070160,61272377).
引文格式: 徐海燕,李小平.基于学习和恶化效应模型的单机调度[J].东南大学学报:自然科学版,2013,43(6):1181-1184. [doi:10.3969/j.issn.1001-0505.2013.06.010]
更新日期/Last Update: 2013-11-20