[1] Yu Xianyu, Zhang Yulin, Zhang Yuhuan, et al. Group scheduling with general position-dependent effect [J]. Journal of Southeast University (English Edition), 2012, 28 (3): 354-359. [doi:10.3969/j.issn.1003-7985.2012.03.018]

Copy

Group scheduling with general position-dependent effect()

带有一般性位置依赖影响的分组调度研究

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

28

Issue:

2012 3

Page:

354-359

Research Field:

Economy and Management

Publishing date:

2012-09-30

Info

Title:

Group scheduling with general position-dependent effect

带有一般性位置依赖影响的分组调度研究

Author(s):

Yu Xianyu^{1, 2}, Zhang Yulin¹, Zhang Yuhuan¹

¹School of Economics and Management, Southeast University, Nanjing 211189, China
²School of Science, East China Institute of Technology, Nanchang 330000, China

虞先玉^{1, 2}, 张玉林¹, 张玉环¹

¹东南大学经济管理学院, 南京 211189; ²东华理工大学理学院, 南昌 330000

Keywords:

group scheduling;  position-dependent;  makespan;  total load

分组调度;  位置依赖;  时间表长;  总负荷

PACS:

F406.2;TP301

DOI:

10.3969/j.issn.1003-7985.2012.03.018

Abstract:

In order to investigate more realistic group scheduling problems with position-dependent effects, the model of general position-dependent group scheduling is proposed, where the actual group setup times and actual processing times are described by general functions of the normal group setup time and position in the sequence. These general functions are not assumed to have specific function structures, and are not restricted to be monotone. By mathematical analysis and proof, each considered problem is decomposed into a group scheduling process and a job scheduling process, and each scheduling process is transferred into the classic assignment problem or the classic single-machine sequence problem, and then the computational complexity to solve the considered problem is analyzed. Analysis results show that, even with general position-dependent job processing times, both the single machine makespan minimization group scheduling problems and the parallel-machine total load minimization group scheduling problems remain polynomially solvable.

为了研究更具实际意义的带有位置依赖影响的分组调度决策问题, 建立了一般性位置依赖的分组调度模型.在模型中, 分组实际发动时间和工件的实际加工时间被表示成初始时间和调度位置的一般函数.此类函数没有被假设为特殊函数形式, 且没有要求限制其函数单调性.通过数理逻辑分析和证明, 把所研究的问题模型分解为组调度过程和工件调度过程, 并把每个调度过程分别转化为经典任务分派问题和单机排序调度问题, 进而分析问题求解的计算复杂度.研究表明, 即使在一般性位置依赖的模型假设下, 单机最小化时间表长的分组调度问题和平行机最小化总负荷的分组调度问题仍然是多项式可解的.

References:

[1] Cheng T C E, Ding Q, Lin B M T. A concise survey of scheduling with time-dependent processing times [J]. European Journal of Operational Research, 2004, 152(1): 1-13.
[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] Janiak A, Rudek R. Experience based approach to scheduling problems with the learning effect [J]. IEEE Transactions on Systems, Man, and Cybernetics—Part A, 2009, 39(2): 344-357.
[4] Yin Y Q, Xu D H, Sun K B, et al. Some scheduling problems with general position-dependent and time-dependent learning effects [J]. Information Science, 2009, 179(14): 2416-2425.
[5] Ng C T, Wang J B, Cheng T C E, et al. Two-machine flow shop scheduling with deteriorating jobs to minimize total completion time [J]. Computers and Operations Research, 2010, 37(1): 83-90.
[6] Ham I, Hitomi K, Yoshida T. Group technology: applications to production management [M]. Boston: Kluwer-Nijhoff, 1985.
[7] Wu C C, Shiau Y R, Lee W C. Single-machine group scheduling problems with deterioration consideration [J]. Computers and Operations Research, 2008, 35(5): 1652-1659.
[8] Yang S J, Yang D L. Single-machine group scheduling problems under the effects of deterioration and learning [J]. Computers and Industrial Engineering, 2010, 58(4): 754-758.
[9] Liu P, Tang L X, Zhou X Y. Two-agent group scheduling with deteriorating jobs on a single machine [J]. International Journal of Advanced Manufacturing Technology, 2010, 47(5): 657-664.
[10] Wang J B, Sun L Y. Single-machine group scheduling with linearly decreasing time-dependent setup times and job processing times [J]. International Journal of Advanced Manufacturing Technology, 2010, 49(5): 765-772.
[11] Lee W C, Wu C C. A note on single-machine group scheduling problems with position-based learning effect [J]. Applied Mathematical Modelling, 2009, 33(4): 2159-2163.
[12] Zhang X G, Yan G L. Single-machine group scheduling problems with deteriorated and learning effect [J]. Applied Mathematics and Computation, 2010, 216(4): 1259-1266.
[13] Wang J B, Wang M Z. A revision of machine scheduling problems with a general learning effect [J]. Mathematical and Computer Modelling, 2011, 53(1): 330-336.
[14] Mosheiov G. Proportionate flowshops with general position-dependent processing times [J]. Information Processing Letters, 2011, 111(4): 174-177.
[15] Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling: a survey [J]. Annals of Discrete Mathematics, 1979, 5: 287-326.
[16] Kuhn H W. The Hungarian method for the assignment problem [J]. Naval Research Logistics Quarterly, 1955, 2: 83-97.
[17] Zhao C L, Tang H Y. Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan [J]. Applied Mathematical Modelling, 2010, 34(3): 837-841.

Memo

Memo:

Biographies: Yu Xianyu(1980—), male, graduate, lecturer; Zhang Yulin(corresponding author), male, doctor, professor, zhangyl@seu.edu.cn.
Foundation items: The National Natural Science Foundation of China(No.71171046), the Scientific Research Innovation Project for College Graduates in Jiangsu Province(No.CXLX_0162).
Citation: Yu Xianyu, Zhang Yulin, Zhang Yuhuan. Group scheduling with general position-dependent effect[J].Journal of Southeast University(English Edition), 2012, 28(3):354-359.[doi:10.3969/j.issn.1003-7985.2012.03.018]

Common functions