Nowadays the airline industry is an important factor in our economy. In this changing market it is important to keep up to date with the latest developments. Especially cost savings, and cost reductions form a vital component to stay competitive in the airline industry. For this work the deicing procedure is studied, which is part of the ground operations. Deicing is of paramount importance to ensure safe flying conditions in wintry conditions. This work considers a deicing at-the-gate operation. In our work we specifically looked at the operation for Aviapartner, which has a relative small operation of five deicing vehicles. On a worst-case day, Aviapartner would have to deice between 30 and 50 aircraft. We hypothesised that proper planning can lead to an improved capacity estimation. We have modelled the deicing operation using a Resource Constrained Project Schedule Problem (RCPSP). This RCPSP is translated into a mixed integer linear program. Using a MILP solver we were able to provide for 94% of the day problem sizes an exact planning. Our implementation provided solutions in acceptable time for a problem size of up to 40 aircraft. To deal with larger problem sizes, we introduced three heuristic algorithms that optimise towards a specific objective (KPI). The second part of the research deals with how we can adopt a planning, such that it can cope with operational concerns. We have modelled three operational concerns: delay of aircraft, weather severity increase, and vehicle breakdown. Finally we have built a proof of concept web implication to interact with plannings from our algorithm.