Paper Titles

Finite Element Analysis and Experimental Study of an Electromagnetic Shell Part with Flow Control Forming
p.2982

Finite Element Analysis of Frame on ZXZ90 Towing Machine for Cable
p.2990

Optimization Design for the Longitudinal Structure of LED Light Guide Plate Using Soft Computing
p.2994

Partial Least Squares Regression Analysis of Thermal Distortion Behavior for Linear Motor Drive Feed System
p.3001

Single-Machine Scheduling to Minimize Makespan with Deterioration Jobs and Multi-Maintenance Activities
p.3007

Solute Distribution Ahead of Interface during Heteroepitaxial Growth
p.3014

The Effect of Damping Block Design on Stability of Ploymer Coextrusion Process
p.3018

The Modal Analysis for the Third Type of Internal Gear Motor
p.3023

The Simulation Study of the Influence of Surface Error on Optical Properties for Optical Part
p.3027

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 690-693Single-Machine Scheduling to Minimize Makespan...

Single-Machine Scheduling to Minimize Makespan with Deterioration Jobs and Multi-Maintenance Activities

Article Preview

Abstract:

This paper explored a single-machine scheduling deterioration jobs with multi-maintenance activities. The non-resumable case and simple linear deterioration effect were taken into account as well. We assumed that after a maintenance activity, the machine will revert to its initial condition and the deterioration effect will start anew. The objective was to minimize the makespan in the system. The problem was proven to be NP-hard in the strong sense. Therefore, a heuristic and a lower bound were introduced and tested numerically. Computational results showed that the proposed algorithm performed well.

You might also be interested in these eBooks

Materials Design, Processing and Applications

Info:

Periodical:

Advanced Materials Research (Volumes 690-693)

Pages:

3007-3013

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.690-693.3007

Citation:

Cite this paper

Online since:

May 2013

Authors:

Chou Jung Hsu, Hung Chi Chen

Keywords:

Deterioration Effect, Make Span, NP-Hard, Scheduling

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

© 2013 Trans Tech Publications Ltd. All Rights Reserved

Share:

Citation:

[1] J.N.D. Gupta and S.K. Gupta. Single facility scheduling with nonlinear processing times. Computers & Industrial Engineering Vol. 14 (1998), pp.387-393.

DOI: 10.1016/0360-8352(88)90041-1

[2] G. Mosheiov. Multi-machine scheduling with linear deterioration. INFOR Vol. 36 (1998), pp.205-214.

DOI: 10.1080/03155986.1998.11732359

[3] A.S., Kunnathur and S.K.. Gupta. Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem. European Journal of Operational Research Vol. 47 (1990), pp.56-64.

DOI: 10.1016/0377-2217(90)90089-t

[4] K.I.J., Ho, J.Y.T. Leung and W.D. Wei. Complexity of scheduling tasks with time-dependent execution times. Information Processing Letters Vol. 48 (1993), pp.315-320.

DOI: 10.1016/0020-0190(93)90175-9

[5] B. Alidaee and N.K. Womer. Scheduling with time dependent processing times: review and extensions. Journal of the Operational Research Society Vol. 50 (1999), pp.711-720.

DOI: 10.1057/palgrave.jors.2600740

[6] T.C.E. Cheng, Q. Ding and B.M.T. Lin. A concise survey of scheduling with time-dependent processing times. European Journal of Operations Research Vol. 152 (2004), pp.1-13.

DOI: 10.1016/s0377-2217(02)00909-8

[7] C.L. Zhao and H.Y. Tang. Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan. Applied Mathematical Modelling Vol. 34 (2010), pp.837-841.

DOI: 10.1016/j.apm.2009.07.002

[8] W.H. Kuo and D.L. Yang. Minimizing the makespan in a single-machine scheduling problem with the cyclic process of an aging effect. Journal of the Operational Research Society Vol. 59 (2008), pp.416-420.

DOI: 10.1057/palgrave.jors.2602363

[9] S.J. Yang and D.L. Yang. Single-machine scheduling problems with aging/deteriorating effect under an optional maintenance activity consideration. INFOR Vol. 48 (2010), pp.171-179.

DOI: 10.3138/infor.48.3.171

[10] S.J. Yang and D.L. Yang. Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities. Omega Vol. 38 (2010), pp.528-533.

DOI: 10.1016/j.omega.2010.01.003

[11] S.J. Yang and D.L. Yang. Minimizing total completion time in single-machine scheduling with aging/deteriorating effects and deteriorating maintenance activities. Computers and Mathematics with Applications Vol. 60 (2010), pp.2161-2169.

DOI: 10.1016/j.camwa.2010.08.003

[12] C.C. Wu and W.C. Lee. Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single-machine. Information Processing Letters Vol. 87 (2003), pp.89-93.

DOI: 10.1016/s0020-0190(03)00262-x

[13] S. Browne and U. Yechiali. Scheduling deteriorating jobs on a single processor. Operations Research Vol. 38 (1990), pp.495-498.

DOI: 10.1287/opre.38.3.495

[14] M. Ji, Y. He and T.C.E. Cheng. Scheduling linear deteriorating jobs with an availability constraint on a single machine. Theoretical Computer Science Vol. 362 (2006), pp.115-126.

DOI: 10.1016/j.tcs.2006.06.006

[15] C. Low, C.J. Hsu and C.T. Su. Minimizing the makespan with an availability constraint on a single machine under simple linear deterioration. Computers & Mathematics with Applications Vol. 56 (2008), pp.257-265.

DOI: 10.1016/j.camwa.2007.12.006

[16] C.J. Hsu, C. Low and C.T. Su. Single-machine scheduling problem with an availability constraint under simple linear deterioration. Journal of Chinese Institute of Industrial Engineers Vol. 27 (2010), pp.189-198.

DOI: 10.1080/10170660903528754

[17] J.S. Chen. Single-machine scheduling with flexible and period maintenance., Journal of the Operational Research Society Vol. 57 (2006), pp.703-710.

[18] C.Y. Lee. Machine scheduling with an availability constraint. Journal of Global Optimization Vol. 9 (1996), pp.395-416.

[19] G. Schmidt. Scheduling with limited machine availability. European Journal of Operational Research Vol. 121 (2000), pp.1-15.

[20] C.C. Wu and W.C. Lee. A note on single-machine scheduling with learning effect and an availability constraint. International Journal of Advance Manufacture Technology Vol. 33 (2007), pp.540-544.

[21] C.Y. Lee and J. Leon. Machine scheduling with a rate-modifying activity. European Journal of Operational Research Vol. 128 (2001), pp.119-128.

DOI: 10.1016/s0377-2217(99)00066-1

[22] D.L. Yang, C.L. Hung, C.J. Hsu and M.S. Chern. Minimizing the makespan in a single-machine scheduling problem with a flexible maintenance, Journal of the Chinese Institute of Industrial Engineers 19 (2002) 63-66.

DOI: 10.1080/10170660209509183

[23] Y., He, M. Ji and T.C.E. Cheng. Single-machine scheduling with a restricted rate-modifying activity. Naval Research Logistics Vol. 52 (2005), pp.361-369.

DOI: 10.1002/nav.20083

[24] C.J. Liao and W.J. Chen. Single-machine scheduling with periodic maintenance and nonresumable jobs. Computers and Operations Research Vol. 30 (2003), pp.1335-1347.

DOI: 10.1016/s0305-0548(02)00074-6

[25] C. Low, M. Ji, C.J. Hsu and C.T. Su. Minimizing the Makespan in a Single Machine Scheduling Problems with Flexible and Periodic Maintenance. Applied Mathematical Modelling Vol. 34 (2009), pp.334-342.

DOI: 10.1016/j.apm.2009.04.014

[26] G.H. Graves and C.Y. Lee. Scheduling maintenance and semiresumable jobs on a single-machine. Naval Research Logistics Vol. 46 (1999), pp.845-863.

DOI: 10.1002/(sici)1520-6750(199910)46:7<845::aid-nav6>3.0.co;2-#

[27] J.S. Chen. Scheduling of nonresumable jobs and flexible maintenance activities on a single-machine to minimize makespan. European Journal of Operations Research Vol. 190 (2008), pp.90-102.

DOI: 10.1016/j.ejor.2007.06.029

[28] W.J. Chen. Minimizing total flow time in the single-machine scheduling problem with periodic maintenance. Journal of the Operational Research Society Vol. 57 (2006), pp.410-415.

DOI: 10.1057/palgrave.jors.2601998

[29] D. Xu, K. Sun and H. Li. A note on "scheduling of nonresumable jobs and flexible maintenance activities on a single-machine to minimize makespan." European Journal of Operations Research Vol. 197 (2009), pp.825-827.

DOI: 10.1016/j.ejor.2008.07.021

[30] H. Wang. A survey of maintenance policies of deterioration systems. European Journal of Operational Research Vol. 139 (2008), pp.469-489.

[31] Y. Ma, C.B. Chu and C. Zuo. A survey of scheduling with deterministic machine availability constraints. Computers & Industrial Engineering Vol. 58 (2010), pp.199-211.

DOI: 10.1016/j.cie.2009.04.014

[32] G. Mosheiov. Scheduling deteriorating jobs under simple linear deterioration. Computers and Operations Research Vol. 21 (1994), pp.653-659.

DOI: 10.1016/0305-0548(94)90080-9

[33] C.T. Ng, M.S. Barketau, T.C.E. Cheng and M.Y. Kovalyov. "Product Partition" and related problems of scheduling and systems reliability: Computational complexity and approximation. European Journal of Operational Research Vol. 207 (2010), pp.601-604.

DOI: 10.1016/j.ejor.2010.05.034