January  2014, 10(1): 243-258. doi: 10.3934/jimo.2014.10.243

A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors

1. 

Laboratory of Theoretical and Applied Computer Science (LITA), University of Lorraine, Ile du Saulcy, 57045, Metz, France, France

2. 

LGIPM, INRIA Costeam, Ecole National d’Ing´enieurs de Metz, France

Received  January 2012 Revised  July 2013 Published  October 2013

In this paper, we introduce a new approach based on DC (Difference of Convex functions) Programming and DCA (DC Algorithm) for minimizing the maintenance cost involving flow-time and tardiness penalties by optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. The main idea is to divide the horizon considered into $H$ intervals. The problem is first formulated as a mixed integer linear problem (MILP) and then reformulated as a DC program. A solution method based on DCA is used to solve the resulting problem. The efficiency of DCA is compared with the algorithm based on the new flow-time and tardiness rule (FTR) given in [1]. The computational results on several test problems show that the solutions provided by DCA are better.
Citation: Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243
References:
[1]

K. H. Adjallah and K. P. Adzakpa, Minimizing maintenance cost involving flow-time and tardiness penalty with unequal release dates,, In Press of Journal of Risk and Reliability, 221 (2007), 57.   Google Scholar

[2]

K. P. Adzakpa, "Maintenance of Distributed Systems: Methods for Real-Time Decision-Making,", PhD Thesis, (2004).   Google Scholar

[3]

M. Berg, The marginal cost analysis and its application to repair and replacement policies,, European Journal of Operational Research, 82 (1995), 214.   Google Scholar

[4]

E. K. Burke and A. J. Smith, Hybrid evolutionary techniques for the maintenance scheduling problem,, Ieee2000 Trans. on Power Systems, 15 (2000), 122.   Google Scholar

[5]

C. Derman, G. J. Lieberman and S. M. Ross, On the optimal assignment of servers and a repairman,, Journal of Applied Probability, 17 (1980), 577.  doi: 10.2307/3213050.  Google Scholar

[6]

C. Duron, M. A. Ould Louly and J.-M. Proth, The one machine scheduling problem: Insertion of a job under the real-time constraint,, European Journal of Operational Research, 199 (2009), 695.  doi: 10.1016/j.ejor.2007.09.048.  Google Scholar

[7]

E. Frostig, Jointly optimal allocation of a repairman and optimal control of service rate for machine repairman problem,, European Journal of Operational Research, 116 (1999), 274.   Google Scholar

[8]

E. Frostig, Optimal allocation of machines to distinguishable repairmen in order to maximize some reward functions,, Probability in the Engineering and Informational Sciences, 9 (1995), 633.  doi: 10.1017/S0269964800004113.  Google Scholar

[9]

E. Frostig, Optimal policies for machine repairmen problems,, Journal of Applied Probability, 30 (1993), 703.  doi: 10.2307/3214776.  Google Scholar

[10]

M. Gopalakrishnan, S. Mohan and Z. He, A tabu search heuristic for preventive maintenance scheduling,, Computers & Industrial Engineering, 40 (2001), 149.   Google Scholar

[11]

G. Graves and C. Lee, Scheduling maintenance and semiresumable jobs on a single machine,, Naval Research Logistics, 46 (1999), 845.   Google Scholar

[12]

G. Koole, Optimal repairman assignment in two symmetric maintenance models, , European Journal of Operational Research, 82 (1995), 295.   Google Scholar

[13]

H. A. Le Thi and T. Pham Dinh, Solving a class of linearly constrained indefinite quadratic problems by DC algorithms,, Journal of Global Optimization, 11 (1997), 253.  doi: 10.1023/A:1008288411710.  Google Scholar

[14]

H. A. Le Thi and T. Pham Dinh, A Continuous approach for globally solving linearly constrained quadratic zero-one programming problem,, Optimization, 50 (2001), 93.  doi: 10.1080/02331930108844555.  Google Scholar

[15]

H. A. Le Thi and T. Pham Dinh, The DC(difference of convex functions) Programming and DCA revisited with DC models of real world non convex optimization problems,, Annals of Operations Research, 133 (2005), 23.  doi: 10.1007/s10479-004-5022-1.  Google Scholar

[16]

H. A. Le Thi, T. Pham Dinh and M. Le Dung, Exact penalty in d.c. programming,, Vietnam Journal of Mathematics, 27 (1999), 169.   Google Scholar

[17]

H. A. Le Thi and T. Pham Dinh, A continuous approach for the concave cost supply problem via DC programming and DCA,, Discrete Applied Mathematics, 156 (2008), 325.  doi: 10.1016/j.dam.2007.03.024.  Google Scholar

[18]

C. Lee and Z. Chen, Scheduling jobs and maintenance activities on parallel machines,, Naval Research Logistics, 47 (2000), 145.  doi: 10.1002/(SICI)1520-6750(200003)47:2<145::AID-NAV5>3.0.CO;2-3.  Google Scholar

[19]

J. Lenstra, A. R. Kan and P. Brucker, Complexity of machine scheduling problems,, Annals of Discrete Mathematics, 1 (1977), 343.   Google Scholar

[20]

Z. Li, H. Liao, L-Y. Chan and A. Elsayed, Maintenance of continuously degrading systems considering random service delays,, Proceedings of the 2008 Industrial Research Conference (IERC), (2008), 17.   Google Scholar

[21]

S-T. Lo, R-M. Chen, Y-M. Huang and C-L. Wu, Multiprocessor system scheduling with precedence and resource constraints using an enhanced ant colony system,, Expert Systems with Applications, 34 (2008), 2071.   Google Scholar

[22]

T. Pham Dinh and H. A. Le Thi, Convex analysis approach to d.c programming: Theory, algorithms and applications,, Acta Mathematica Vietnamica, 22 (1997), 289.   Google Scholar

[23]

T. Pham Dinh and H. A. Le Thi, DC optimization algorihms for solving the trust region subproblem,, SIAM J.Optimization, 8 (1997), 476.   Google Scholar

[24]

K. Park, Optimal number of minimal repairs before replacement,, IEEE Transactions on Reliability, R-28 (1979), 137.   Google Scholar

[25]

X. Qi, T. Chen and F. Tu, Scheduling the maintenance on a single machine,, Journal of the Operation Research Society, 50 (1999), 1071.   Google Scholar

[26]

R.T. Rockafellar, "Convex analysis Princeton University Press,", Princeton University Press, (1970).   Google Scholar

[27]

S. Seshadri, Determination of aggregate preventive maintenance programs using production schedules,, Computers and Industrial Engineering, 14 (1988), 193.   Google Scholar

[28]

W. Stadje and D. Zuckerman, Optimal repair policies with general degree of repair in two maintenance models,, Operations Research Letters, 11 (1992), 77.  doi: 10.1016/0167-6377(92)90036-3.  Google Scholar

[29]

H. Tajima, J. Sugimoto, T. Funabashi and R. Yokoyama, Auction price-based thermal unit maintenance scheduling by reactive tabu search,, Proc. 41st IEEE Int. UPEC'06 (Universities Power Engineering Conference), (2006).   Google Scholar

[30]

L. Weinstein and C. Chung, Integrating maintenance and production decisions in a hierarchical production planning environment,, Computer and Operations Research, 26 (1999), 1059.   Google Scholar

show all references

References:
[1]

K. H. Adjallah and K. P. Adzakpa, Minimizing maintenance cost involving flow-time and tardiness penalty with unequal release dates,, In Press of Journal of Risk and Reliability, 221 (2007), 57.   Google Scholar

[2]

K. P. Adzakpa, "Maintenance of Distributed Systems: Methods for Real-Time Decision-Making,", PhD Thesis, (2004).   Google Scholar

[3]

M. Berg, The marginal cost analysis and its application to repair and replacement policies,, European Journal of Operational Research, 82 (1995), 214.   Google Scholar

[4]

E. K. Burke and A. J. Smith, Hybrid evolutionary techniques for the maintenance scheduling problem,, Ieee2000 Trans. on Power Systems, 15 (2000), 122.   Google Scholar

[5]

C. Derman, G. J. Lieberman and S. M. Ross, On the optimal assignment of servers and a repairman,, Journal of Applied Probability, 17 (1980), 577.  doi: 10.2307/3213050.  Google Scholar

[6]

C. Duron, M. A. Ould Louly and J.-M. Proth, The one machine scheduling problem: Insertion of a job under the real-time constraint,, European Journal of Operational Research, 199 (2009), 695.  doi: 10.1016/j.ejor.2007.09.048.  Google Scholar

[7]

E. Frostig, Jointly optimal allocation of a repairman and optimal control of service rate for machine repairman problem,, European Journal of Operational Research, 116 (1999), 274.   Google Scholar

[8]

E. Frostig, Optimal allocation of machines to distinguishable repairmen in order to maximize some reward functions,, Probability in the Engineering and Informational Sciences, 9 (1995), 633.  doi: 10.1017/S0269964800004113.  Google Scholar

[9]

E. Frostig, Optimal policies for machine repairmen problems,, Journal of Applied Probability, 30 (1993), 703.  doi: 10.2307/3214776.  Google Scholar

[10]

M. Gopalakrishnan, S. Mohan and Z. He, A tabu search heuristic for preventive maintenance scheduling,, Computers & Industrial Engineering, 40 (2001), 149.   Google Scholar

[11]

G. Graves and C. Lee, Scheduling maintenance and semiresumable jobs on a single machine,, Naval Research Logistics, 46 (1999), 845.   Google Scholar

[12]

G. Koole, Optimal repairman assignment in two symmetric maintenance models, , European Journal of Operational Research, 82 (1995), 295.   Google Scholar

[13]

H. A. Le Thi and T. Pham Dinh, Solving a class of linearly constrained indefinite quadratic problems by DC algorithms,, Journal of Global Optimization, 11 (1997), 253.  doi: 10.1023/A:1008288411710.  Google Scholar

[14]

H. A. Le Thi and T. Pham Dinh, A Continuous approach for globally solving linearly constrained quadratic zero-one programming problem,, Optimization, 50 (2001), 93.  doi: 10.1080/02331930108844555.  Google Scholar

[15]

H. A. Le Thi and T. Pham Dinh, The DC(difference of convex functions) Programming and DCA revisited with DC models of real world non convex optimization problems,, Annals of Operations Research, 133 (2005), 23.  doi: 10.1007/s10479-004-5022-1.  Google Scholar

[16]

H. A. Le Thi, T. Pham Dinh and M. Le Dung, Exact penalty in d.c. programming,, Vietnam Journal of Mathematics, 27 (1999), 169.   Google Scholar

[17]

H. A. Le Thi and T. Pham Dinh, A continuous approach for the concave cost supply problem via DC programming and DCA,, Discrete Applied Mathematics, 156 (2008), 325.  doi: 10.1016/j.dam.2007.03.024.  Google Scholar

[18]

C. Lee and Z. Chen, Scheduling jobs and maintenance activities on parallel machines,, Naval Research Logistics, 47 (2000), 145.  doi: 10.1002/(SICI)1520-6750(200003)47:2<145::AID-NAV5>3.0.CO;2-3.  Google Scholar

[19]

J. Lenstra, A. R. Kan and P. Brucker, Complexity of machine scheduling problems,, Annals of Discrete Mathematics, 1 (1977), 343.   Google Scholar

[20]

Z. Li, H. Liao, L-Y. Chan and A. Elsayed, Maintenance of continuously degrading systems considering random service delays,, Proceedings of the 2008 Industrial Research Conference (IERC), (2008), 17.   Google Scholar

[21]

S-T. Lo, R-M. Chen, Y-M. Huang and C-L. Wu, Multiprocessor system scheduling with precedence and resource constraints using an enhanced ant colony system,, Expert Systems with Applications, 34 (2008), 2071.   Google Scholar

[22]

T. Pham Dinh and H. A. Le Thi, Convex analysis approach to d.c programming: Theory, algorithms and applications,, Acta Mathematica Vietnamica, 22 (1997), 289.   Google Scholar

[23]

T. Pham Dinh and H. A. Le Thi, DC optimization algorihms for solving the trust region subproblem,, SIAM J.Optimization, 8 (1997), 476.   Google Scholar

[24]

K. Park, Optimal number of minimal repairs before replacement,, IEEE Transactions on Reliability, R-28 (1979), 137.   Google Scholar

[25]

X. Qi, T. Chen and F. Tu, Scheduling the maintenance on a single machine,, Journal of the Operation Research Society, 50 (1999), 1071.   Google Scholar

[26]

R.T. Rockafellar, "Convex analysis Princeton University Press,", Princeton University Press, (1970).   Google Scholar

[27]

S. Seshadri, Determination of aggregate preventive maintenance programs using production schedules,, Computers and Industrial Engineering, 14 (1988), 193.   Google Scholar

[28]

W. Stadje and D. Zuckerman, Optimal repair policies with general degree of repair in two maintenance models,, Operations Research Letters, 11 (1992), 77.  doi: 10.1016/0167-6377(92)90036-3.  Google Scholar

[29]

H. Tajima, J. Sugimoto, T. Funabashi and R. Yokoyama, Auction price-based thermal unit maintenance scheduling by reactive tabu search,, Proc. 41st IEEE Int. UPEC'06 (Universities Power Engineering Conference), (2006).   Google Scholar

[30]

L. Weinstein and C. Chung, Integrating maintenance and production decisions in a hierarchical production planning environment,, Computer and Operations Research, 26 (1999), 1059.   Google Scholar

[1]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[2]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[3]

Shu-Yu Hsu. Existence and properties of ancient solutions of the Yamabe flow. Discrete & Continuous Dynamical Systems - A, 2018, 38 (1) : 91-129. doi: 10.3934/dcds.2018005

[4]

Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355

[5]

Feng Luo. A combinatorial curvature flow for compact 3-manifolds with boundary. Electronic Research Announcements, 2005, 11: 12-20.

[6]

Cécile Carrère, Grégoire Nadin. Influence of mutations in phenotypically-structured populations in time periodic environment. Discrete & Continuous Dynamical Systems - B, 2020, 25 (9) : 3609-3630. doi: 10.3934/dcdsb.2020075

[7]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183

[8]

Guillermo Reyes, Juan-Luis Vázquez. Long time behavior for the inhomogeneous PME in a medium with slowly decaying density. Communications on Pure & Applied Analysis, 2009, 8 (2) : 493-508. doi: 10.3934/cpaa.2009.8.493

[9]

Wei-Jian Bo, Guo Lin, Shigui Ruan. Traveling wave solutions for time periodic reaction-diffusion systems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (9) : 4329-4351. doi: 10.3934/dcds.2018189

[10]

Kin Ming Hui, Soojung Kim. Asymptotic large time behavior of singular solutions of the fast diffusion equation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (11) : 5943-5977. doi: 10.3934/dcds.2017258

[11]

Peter Benner, Jens Saak, M. Monir Uddin. Balancing based model reduction for structured index-2 unstable descriptor systems with application to flow control. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 1-20. doi: 10.3934/naco.2016.6.1

[12]

Tomáš Roubíček. An energy-conserving time-discretisation scheme for poroelastic media with phase-field fracture emitting waves and heat. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 867-893. doi: 10.3934/dcdss.2017044

[13]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (38)
  • HTML views (0)
  • Cited by (1)

[Back to Top]