[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¹;  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

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