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.

[2]

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

[3]

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

[4]

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

[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.

[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.

[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.

[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.

[9]

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

[10]

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

[11]

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

[12]

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

[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.

[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.

[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.

[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.

[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.

[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.

[19]

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

[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.

[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.

[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.

[23]

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

[24]

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

[25]

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

[26]

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

[27]

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

[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.

[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).

[30]

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

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.

[2]

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

[3]

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

[4]

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

[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.

[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.

[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.

[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.

[9]

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

[10]

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

[11]

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

[12]

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

[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.

[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.

[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.

[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.

[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.

[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.

[19]

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

[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.

[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.

[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.

[23]

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

[24]

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

[25]

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

[26]

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

[27]

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

[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.

[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).

[30]

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

[1]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703

[2]

Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial & Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825

[3]

Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391

[4]

Adel Dabah, Ahcene Bendjoudi, Abdelhakim AitZai. An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029

[5]

Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-34. doi: 10.3934/jimo.2019030

[6]

Ethel Mokotoff. Algorithms for bicriteria minimization in the permutation flow shop scheduling problem. Journal of Industrial & Management Optimization, 2011, 7 (1) : 253-282. doi: 10.3934/jimo.2011.7.253

[7]

Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial & Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705

[8]

Wen-Hung Wu, Yunqiang Yin, Wen-Hsiang Wu, Chin-Chia Wu, Peng-Hsiang Hsu. A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents. Journal of Industrial & Management Optimization, 2014, 10 (2) : 591-611. doi: 10.3934/jimo.2014.10.591

[9]

Ji-Bo Wang, Mengqi Liu, Na Yin, Ping Ji. Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1025-1039. doi: 10.3934/jimo.2016060

[10]

Ping Yan, Ji-Bo Wang, Li-Qiang Zhao. Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088

[11]

Zhao-Hong Jia, Ting-Ting Wen, Joseph Y.-T. Leung, Kai Li. Effective heuristics for makespan minimization in parallel batch machines with non-identical capacities and job release times. Journal of Industrial & Management Optimization, 2017, 13 (2) : 977-993. doi: 10.3934/jimo.2016057

[12]

M. Ramasubramaniam, M. Mathirajan. A solution framework for scheduling a BPM with non-identical job dimensions. Journal of Industrial & Management Optimization, 2007, 3 (3) : 445-456. doi: 10.3934/jimo.2007.3.445

[13]

Chuanli Zhao, Yunqiang Yin, T. C. E. Cheng, Chin-Chia Wu. Single-machine scheduling and due date assignment with rejection and position-dependent processing times. Journal of Industrial & Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691

[14]

Hongwei Li, Yuvraj Gajpal, C. R. Bector. A survey of due-date related single-machine with two-agent scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-19. doi: 10.3934/jimo.2019005

[15]

Changzhi Wu, Chaojie Li, Qiang Long. A DC programming approach for sensor network localization with uncertainties in anchor positions. Journal of Industrial & Management Optimization, 2014, 10 (3) : 817-826. doi: 10.3934/jimo.2014.10.817

[16]

Jian Gu, Xiantao Xiao, Liwei Zhang. A subgradient-based convex approximations method for DC programming and its applications. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1349-1366. doi: 10.3934/jimo.2016.12.1349

[17]

Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071

[18]

Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017

[19]

Wan Nor Ashikin Wan Ahmad Fatthi, Adibah Shuib, Rosma Mohd Dom. A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse. Journal of Industrial & Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431

[20]

Le Thi Hoai An, Tran Duc Quynh, Pham Dinh Tao. A DC programming approach for a class of bilevel programming problems and its application in Portfolio Selection. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 167-185. doi: 10.3934/naco.2012.2.167

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (8)
  • HTML views (0)
  • Cited by (0)

[Back to Top]