We consider a class of scheduling problems of n weighted tasks on M identical, and parallel processors with an objective of minimizing the sum of the tasks weighted flow-times. A priority rule for total weighted flow-time (PRTWF), is then proposed for locally optimal scheduling of tasks with unequal release dates and processing times. Then, an algorithm based on a heuristic and the PRTWF, is worked out to minimize the total weighted flow-time of the given set of tasks on a single server. This algorithm is designed for implementation in a dynamic process of real-time decision-making. It is next extended to tasks scheduling (with unequal release dates and processing times) on parallel servers, while minimizing their total weighted flow-time. A lower bound of solutions is also proposed to evaluate the algorithm, with a complexity in O(n3) in the off-line scheduling process. The rule is then used in an algorithm of on-line planning and scheduling of maintenance tasks in a large size distributed system with weighted Equipments.
In several areas of activity as in maintenance, delays in starting tasks engender, for the user, extra costs due to the degradations of Equipments, raw materials and products' quality, and disorganization of the production process. Such cost may be very high in some cases, particularly in maintenance tasks management for several reasons: the considered tasks are not always available from the initial time t0 before the decision-making times t; in some cases, tasks cannot be started before a given date which marks the beginning of inescapable degradations, etc. As a result, the processing of many tasks may be delayed in relation to their release dates. Under these conditions, the costs include additional costs due to delayed completion of tasks. It is then necessary, in this case, to set up a real-time decision making strategy to manage tasks.
Obviously, these costs increase with the flow-times of worsening operation conditions. A way to reduce these costs is to schedule tasks so as to minimize their flow-times in penalizing situations. When the additive cost increases uniformly and in an identical way for all the tasks, the problem consists in minimizing, through optimal scheduling, the sum of the flow-times of all the tasks in penalizing situations.
Works addressing the typical problem of maintaining optimal task scheduling and processors allocation are rare in the existing literature. We mention Weinstein and Chung [27] who proposed a mixed-integer linear model which incorporates preventive maintenance into the production policies. This method aims at minimizing the cost and the deviation of production tasks in contrast to maintenance free production policies. In regards to preventive maintenance, we also mention the heuristic method of Qi et al. [17] based on the Shortest Processing Time (SPT) priority rule to minimize the makespan in a production policy. They studied the parallel-machines scheduling problem where preventive maintenance tasks are performed on each machine, just as in Lee and Chen [15] and Graves and Lee [13]. Lee and Chen [15], Qi et al. [17] proposed a branch and bound method to minimize weighted completion time of tasks based on the partition formulation of the problem.
In Ref. [1], we proposed an on-line algorithm for real-time maintenance planning and scheduling methods on a given horizon. In the given algorithm, tasks are scheduled in real-time, and the precedence constraints linking the different tasks on the same Equipment have been dealt with. But the existing methods in production are quite limited where the maintenance assets' sensitivity (importance) and tasks' set-up time are concerned. In this paper, we propose a priority rule for the total weighted flow-time. This rule, which considers task pairs, has very good properties. It can be used as well in production as in maintenance activities planning and scheduling. On this basis, we propose an algorithm for maintenance tasks real-time scheduling and resources allocation.
In the continuation of this paper, we state in Section 2 the real-time maintenance decision making problem and the link to a scheduling problem of weighted tasks with unequal release dates. In order to solve it, Section 3 is devoted to a static (off-line) approach to the scheduling problem. A local optimality priority rule ((Priority Rule for Total Weighted Flow-time, PRTWF) is proposed, proved and compared to existing rules in the literature in this section. In Section 4, we adapted the approach to the real-time maintenance decision making process. Experimentations are provided in Section 5 and finally Section 6 concludes and proposes future extensions to this work.
We presented in this paper an efficient algorithm for on-line tasks scheduling in a distributed system. The tasks are weighted relatively to their sensitivity or importance. We proposed a method based on a priority rule (PRTWF—Priority Rule for Total Weighted Flow-time). We proved that this rule is locally optimal for the total weighted flow-time minimization, and defined the different related concepts and spelled out the underlying properties. We also identified a lower bound which allows the rule's performance evaluation. The problem under consideration is NP-hard and existing literature proposes just a limited number of methods for solving the weighted flow-time minimization problem. The PRTWF function is of polynomial computational complexity, and this has been confirmed by the CPU computation times. This approach is adapted, with additional concepts, to real-time maintenance decision making in large size distributed systems. In extension to this work, we will propose approaches to solve the problem, first in the case of tasks with unequal release dates and set-up times, and next in the case of tasks with unequal release dates, set-up times and weights while adapting them to the maintenance decision making.
