Hierarchical planning and scheduling

Řídicí technika a robotika

The main benefit of hierarchical planning and scheduling is that at each decision layer, only the most relevant information is used. E.g., when taking planning decisions, resource capacities are aggregated and the fine details of dealing with single resources are neglected. In contrast, when solving scheduling problems, only the weekly or daily assignments have to be scheduled [Kis2012]. However, these two types of decisions are strongly related and therefore only an efficient communication between the decision layers can guarantee successful method application.

The considered problem is RCPSP (Resource Constrained Project Scheduling Problem) with/without alternatives [Capek2012]. It is characterized by a set of activities to be planned and scheduled. Order of these activities is partly defined by precedence constraints. Each activity requires some amount of the resources while every resource has planned capacity. The goal is to find a sequence of the planned activities and capacity of resources (i.e. a schedule) with respect to two criteria. One objective is to minimize the earliness/tardiness penalty (costs incurred by completing some of the jobs before or after their due-dates). The second objective is to minimize costs connected with increasing capacity of resources (e.g. hiring more employees or working overtime). Then the solution of the problem is a Pareto front considering these two objectives.

 For solving the above described problem, the first step will be to design a centralized and exact algorithm. The second step will be to propose a distributed hierarchical algorithm and to compare their performance with respect to the centralized one. In the case of the hierarchical algorithm the objective is to define the problem decomposition into layers and an efficient communication protocol between them. There are two requirements applied on the protocol. On one hand, the protocol has to carry enough information to allow the algorithm to find perspective solutions. On the other hand it should carry the only information needed to minimize the communication bandwidth.

  • [Kis2012] T. Kis, A. Kovacs, A cutting plane approach for integrated planning and scheduling, Computers & Operations Research, Volume 39, Issue 2, February 2012, Pages 320-327.
  • [Capek2012] R. Capek, P. Sucha, Z. Hanzalek, Production scheduling with alternative process plans, European Journal of Operational Research, Volume 217, Issue 2, 1 March 2012, Pages 300-311

Required skills: good background in operational research or combinatorial optimization. Knowledge of scheduling and or distributed algorithms is an advantage.