基于加工时间之和学习效应下的单机成组排序问题

运筹学学报 ›› 2013, Vol. 17 ›› Issue (1): 98-105.

基于加工时间之和学习效应下的单机成组排序问题

张新功¹

1. 重庆师范大学数学科学学院

出版日期:2013-03-15 发布日期:2013-03-15
通讯作者: 张新功 E-mail: zhangxg7980@yahoo.com.cn

Single-machine group scheduling problems with the sum-of-processing-time based on learning effect

ZHANG Xingong¹

1. College of Mathematics Science, Chongqing Normal University

Online:2013-03-15 Published:2013-03-15

摘要/Abstract

摘要： 研究具有加工时间之和学习效应下的一个新型成组排序问题，工件的学习效应是之前工件加工时间之和的函数，组学习效应是成组加工所在的位置的函数. 考虑最大完工时间和总完工时间两个问题，证明了这两个问题都是多项式时间可解的，并提出了相应的多项式时间算法.

关键词: 单机排序, 学习效应, 成组技术, 时间表长, 总完工时间

Abstract: This paper investigates a new group scheduling problem with sum-of-processing-time based learning effect. The learning effect of a job is assumed to be a function of total processing times of jobs scheduled in front of it, the learning effect of group is assumed to a function of its position in the sequence. The goal is to minimize makespan and the total completion times under the proposed model, respectively. Some optimal properties and optimal polynomial time algorithms to solve these problems are also provided.

Key words: single-machine, learning effect, group technology, makespan, total completion time

张新功. 基于加工时间之和学习效应下的单机成组排序问题[J]. 运筹学学报, 2013, 17(1): 98-105.

ZHANG Xingong. Single-machine group scheduling problems with the sum-of-processing-time based on learning effect[J]. Operations Research Transactions, 2013, 17(1): 98-105.

参考文献

Heiser J, Render B. Operations Management [M]. Prentice Hall: Englewood Cliffs, NJ, 1999.
Russell R, Taylor B W III. Operations Management: Multimedia Version [M]. Prentice Hall: Upper Saddle River, NJ, 2000.
Biskup D. Single-machines scheduling with learning considerations [J]. European of Journal Operation Research, 1999, 115: 173-178.
Cheng T C E, Wang G. Single machine with learning effect considerations [J]. Annals of Operations Research, 2000, 98: 273-290.
Mosheiov G. Scheduling problems with a learning effect [J]. European Journal of Operational Research, 2001, 132: 687-693.
Mosheiov G, Sidney J B. Scheduling with general job-dependent learning curves [J]. European Journal of Operational Research, 2003, 147: 665-670.
Biskup D. A state-of-the-art review on scheduling with learning effects [J]. European Journal of Operational Research. 2008, 188: 315-329.
Cheng T C E, Lai P J, Wu C C, et al. Single-machine scheduling with sum-of-logarithm-processing-times-based learning considerations [J]. Information Sciences, 2009, 179: 3127-3135.
Zhang X, Yan G. Single-machine scheduling problems with general learning effect [J]. OR Transactions, 2009, 13(4): 56-64.
Ham I, Hitomi K, Yoshida T. Group technology: applications to production management [M]. Boston: Kluwer-Nijhoff, 1985.
Allahverdi A, Gupta J N D, Aldowaisan T. A review of scheduling research involving setup considerations [J]. Omega, 1999, 27: 219-239.
Cheng T C E, Kovalyov M Y, Tuzikov A V. Single machine group scheduling with ordered criteria [J]. Journal of the Operational Research Society, 1996, 47: 315-320.
Lee W C, Wu C C. A note on single-machine group scheduling problems with position-based learning effect [J]. Applied Mathematical Modelling, 2009, 334(2): 159-2163.
Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling: a survey [J]. Ann Discrete Math, 1979, 5: 287-326.
Wu C C, Lee W C. Single-machine and flowshop scheduling with a general learning effect model [J]. Computers and Industrial Engineering, 2009, 56: 1553-1558.

[1]	赵聪聪, 方丹丹, 李荣珩. 具有学习效应的两台机上最优混合流水作业算法[J]. 运筹学学报, 2020, 24(2): 42-60.
[2]	赵晓成, 李大刚. 机器和工人都有加工资质约束的平行机排序问题研究[J]. 运筹学学报, 2018, 22(3): 99-108.
[3]	酒明珠, 高园, 原晋江. 工件可自由下线最小化总完工时间的平行分批排序问题[J]. 运筹学学报, 2018, 22(1): 32-41.
[4]	朱征露, 鲁习文. 带学习效应的两台平行机时间表长问题[J]. 运筹学学报, 2018, 22(1): 55-66.
[5]	刘颖, 张新功. 具有学习效应的三层供应链排序问题[J]. 运筹学学报, 2016, 20(1): 31-42.