[1] Liu Biyu, Chen Weida,. Single-machine scheduling with preventive periodic maintenanceand resumable jobs in remanufacturing system [J]. Journal of Southeast University (English Edition), 2012, 28 (3): 349-353. [doi:10.3969/j.issn.1003-7985.2012.03.017]

Copy

Single-machine scheduling with preventive periodic maintenanceand resumable jobs in remanufacturing system()

预防性周期维护下考虑可中断工件的再制造单机调度

Share：

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

Volumn:

28

Issue:

2012 3

Page:

349-353

Research Field:

Economy and Management

Publishing date:

2012-09-30

Info

Title:

Single-machine scheduling with preventive periodic maintenanceand resumable jobs in remanufacturing system

预防性周期维护下考虑可中断工件的再制造单机调度

Author(s):

Liu Biyu^{1, 2}, Chen Weida¹

¹School of Economics and Management, Southeast University, Nanjing 211189, China
²School of Management Science and Engineering, Anhui University of Technology, Maanshan 243000, China

刘碧玉^{1, 2}, 陈伟达¹

¹东南大学经济管理学院, 南京211189; ²安徽工业大学管理科学与工程学院, 马鞍山243000

Keywords:

single-machine scheduling;  preventive periodic maintenance;  resumable jobs;  LPT-LS algorithm

单机调度;  预防性周期维护;  可中断工件;  LPT-LS算法

PACS:

F273

DOI:

10.3969/j.issn.1003-7985.2012.03.017

Abstract:

A single-machine scheduling with preventive periodic maintenance activities in a remanufacturing system including resumable and non-resumable jobs is studied. The objective is to find a schedule to minimize the makespan and an LPT-LS algorithm is proposed. Non-resumable jobs are first scheduled in a machine by the longest processing time(LPT)rule, and then resumable jobs are scheduled by the list scheduling(LS)rule. And the worst-case ratios of this algorithm in three different cases in terms of the value of the total processing time of the resumable jobs(denoted as S₂)are discussed. When S₂ is longer than the spare time of the machine after the non-resumable jobs are assigned by the LPT rule, it is equal to 1. When S₂ falls in between the spare time of the machine by the LPT rule and the optimal schedule rule, it is less than 2. When S₂ is less than the spare time of the machine by the optimal schedule rule, it is less than 2. Finally, numerical examples are presented for verification.

研究预防性周期维护策略下再制造系统中可中断和不可中断2类工件的单机调度问题.以最小化完工时间为目标, 提出了LPT-LS算法, 该算法首先按LPT(longest processing time)规则安排不可中断工件, 然后按LS(list scheduling)规则安排可中断工件.并根据可中断工件的总加工时间(记为S₂)分3种情况证明了该算法的最坏情况比, 结论如下:当S₂大于按LPT规则安排不可中断工件后机器的空闲时间时, 最坏情况比为1;当S₂介于分别按LPT规则和OPT(最优排序)规则安排不可中断工件后机器的空闲时间之间时, 最坏情况比小于2;当S₂小于按OPT规则安排不可中断工件后机器的空闲时间时, 最坏情况比小于2.最后通过算例验证了结论的正确性.

References:

[1] Tang O, Grubbstr O M R W, Zanoni S. Planned lead time determination in a make-to-order remanufacturing system [J]. International Journal of Production Economics, 2007, 108(1/2): 426-435.
[2] Arts R H P M, Knapp G M, Mann Jr L. Some aspects of measuring maintenance in the process industry [J]. Journal of Quality in Maintenance Engineering, 1998, 4(1):6-11.
[3] Liao C J, Chen W J. Single-machine scheduling with periodic maintenance and nonresumable jobs [J]. Computers and Operations Research, 2003, 30(9):1335-1347.
[4] Lee C Y. Machine scheduling with an availability constraint [J]. Journal of Global Optimization, 1996, 9(3/4):395-416.
[5] Lee C Y, Liman S D. Single machine flow-time scheduling with scheduled maintenance [J]. Acta Informatica, 1992, 29(4):375-382.
[6] Graves G H, Lee C Y. Scheduling maintenance and semiresumable jobs on a single machine [J]. Naval Research Logistics, 1999, 46(7):845-863.
[7] Ma Y, Yang S L, Chu C B. Minimizing makespan in semiresumable case of single-machine scheduling with an availability constraint [J]. Systems Engineering—Theory & Practice, 2009, 29(4): 128-134.
[8] Chen W J. Minimizing number of tardy jobs on a single machine subject to periodic maintenance [J]. Omega, 2009, 37(3):591-599.
[9] Wu C C, Lee W C. A note on single-machine scheduling with learning effect and an availability constraint [J]. The International Journal of Advanced Manufacturing Technology, 2007, 33(5/6): 540-544.
[10] Yang S J, Yang D L. Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities [J]. Omega, 2010, 38(6): 528-533.
[11] Ji M, He Y, Cheng T C E. Single-machine scheduling with periodic maintenance to minimize makespan [J]. Computers & Operations Research, 2007, 34(6): 1764-1770.
[12] 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.

Memo

Memo:

Biographies: Liu Biyu(1981—), female, graduate, lecturer; Chen Weida(corresponding author), male, doctor, professor, cwd@seu.edu.cn.
Foundation items: The National Natural Science Foundation of China(No.70971022, 71271054), the Scientific Research Innovation Project for College Graduates in Jiangsu Province(No.CXLX_-0157), the Scientific Research Foundation of the Education Department of Anhui Province(No.2011sk123).
Citation: Liu Biyu, Chen Weida. Single-machine scheduling with preventive periodic maintenance and resumable jobs in remanufacturing system[J].Journal of Southeast University(English Edition), 2012, 28(3):349-353.[doi:10.3969/j.issn.1003-7985.2012.03.017]

Common functions