On-line maintenance job scheduling and assignment to resources in distributed systems by heuristic-based optimization
Tóm tắt
A heuristic-based optimization algorithm is proposed in this paper for on-line scheduling and assignment of preventive maintenance jobs to processors, to minimize under availability constraints, on a given time-window, the total cost of the maintenance operations of a distributed system. This algorithm minimizes the cost of discharge of preventive maintenance tasks or jobs, while assigning the tasks along with balancing the processors load. It is shown that the problem is NP-hard. To solve it, the concept of job emergency is introduced and the priority rule for total flow time (PRTF) criterion is used in an adapted heuristic job-scheduling model. In addition, the algorithm considers the constraints of precedence among consecutive standby jobs and their emergency. It is depicted the specific properties of the proposed heuristic allowing jobs scheduling in the right order. Computational results illustrate the efficiency of the approach implemented on different system configurations.
Tài liệu tham khảo
Berg, M. P. (1995) The marginal cost analysis and its application to repair and replacement policies. European Journal of Operational Research, 82, 214–224.
Bonnour, M., Bloch, C. and Zerhouni, N. (2001) Modélisation intégrée de maintenance et de production, MOSIM' 01, Actes de la Troisième Conférence Francophone de MOdélisation et SIMulation, Troyes, France, 25–27 Avril 2001, pp. 805–810.
Bruno, J., Coffman, E. G. and Sethi, R. (1974) Scheduling independent jobs to reduce mean finishing time. Communications of ACM, 17, 7.
Calibra, R., Pulcini, G. and Rapone, M. (1995) Optimal reliability and maintainability allocation in manufacturing systems. Quality and Reliability Engineering International, 11, 183–188.
Chu, C. (1990) One-machine scheduling for minimizing total flow time with release dates. Proceedings of Rensselaer's Second Conference on CIM, Troy, NY, 21–23 May, pp. 570–576.
Chu, C. (1992) A branch-and-bound algorithm to minimize total flow time with unequal release dates. Naval Research Logistics, 39, 859–875.
Derman, C., Lieberman, G. J. and Ross, S. M. (1980) On the optimal assignment of servers and a repairman. Journal of Applied Probability, 17, 703–715.
Du, J., Leung, J.Y-T. and Young, G. H. (1991) Scheduling chain structured jobs to minimize makespan and mean flowtime. Information and Computation, 92, 219–236.
Frostig, E. (1993) Optimal policies for machine repairman problems. Journal of Applied Probability, 30, 703–715.
Frostig, E. (1995) Optimal allocation of machine repairman in order to maximize some reward functions. Probability in the Engineering and Informational Services, 9, 633–645.
Frostig, E. (1999) Jointly optimal allocation of a repairman and optimal control of service rate for machine repairman problem. European Journal of Operational Research, 116, 274–280.
Fyffe, D. E., Hines, W. W. and Kee Lee, N. (1968) System reliability allocation and a computational algorithm. IEEE Transactions on Reliability, R-17, 64–69.
Graves, G. H. and Lee, C. Y. (1999) Scheduling maintenance and semi-resumable jobs on a single machine. Naval Research Logistics, 46, 845–863.
Koole, G. (1995) Optimal repairman assignment in two symmetric maintenance models. European Journal of Operational Research, 82, 295–301.
Lam, Y. (1999) An optimal maintenance model for a combination of secondhand new or outdated updated system. European Journal of Operational Research, 119, 274–280.
Lee, C. Y. and Chen, Z. L. (2000) Scheduling jobs and maintenance activities on parallel machines. Naval Research Logistics, 47, 145–165.
Lenstra, J. K., Rinnooy Kan, A. H. G. and Brucker (1977) Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343–362.
Park, K. S. (1979) Optimal number of minimal repair before replacement. IEEE Transactions on Reliability, 28(2), 137–140.
Qi, X., Chen, T. and Tu, F. (1999) Scheduling the maintenance on a single machine. Journal of the Operation Research Society, 50(10), 1071–1078.
Seshadri, S. and Pinedo, M. (1999) Optimal allocation of processors in a job shop environment. IIE Transactions, 31, 195–206.
Sinuany-Stern, Z. (1999) Reliability and maintenance in production control. Annals of Operations Research, 91, Kluwer Academic Publishers, The Netherlands.
Stadje, W. and Zuckerman, D. (1992) Optimal repair policies with general degree of repair in two maintenance model. Optimal Research Letters, 11, 77–80.
Villemeur, A. (1992) Reliability, Availability, Maintainability and Safety Assessment, John Wiley, UK.
Weinstein, L. and Chung, C. H. (1999) Integrating maintenance and production decision in a hierarchical production planning. Computer and Operations Research, 26, 1059–1074.
Yalaoui, F. (2000) Ordonancement de la production en presence de machines interactives, Ph.D. thesis, University of Technology of Troyes, 146 pp.