2010 Honours Project
Antarctica New Zealand was established in 1996 as a crown entity responsible for developing, managing and executing New Zealand government activities in Antarctica and the southern ocean. Their key activities include supporting scientific research, conserving the intrinsic values of Antarctica and the southern ocean and raising public awareness of the international significance of the continent. Antarctica NZ maintains New Zealand’s operational presence in the Ross Dependency for possible future economic benefits and for future generations. The organisation is purely project based; meaning that scheduling projects, while keeping within resource constraints, is crucial for the operations of Antarctica NZ.
New Zealand’s station in Antarctica is Scott Base, the transition point to the field. Preselected events are scheduled to travel to Antarctica in a season that runs from October to February. During this time Scott Base staff must accommodate and support the events. Each of the groups has different purposes to fulfil in Antarctica and therefore need different resources at different times. Issues that are encountered with scheduling the events to travel to Antarctica are limited resources, restrictions on the days that events may travel and trying to change the schedule to accommodate event changes or additional events. There are also uncertainties involved with travel to Antarctica, such as weather, which can require changes to the event schedule and increase the complexity of the scheduling problem.
This project is looking to overcome the identified issues of the previous project to supply Antarctica NZ with a model that will be a good representation of their needs and will be of practical use to them. The model developed in this project takes the form of a heuristic. The heuristic is aimed at gaining an initial event scheduling solution that is feasible with respect to the resource constraints. The heuristic developed has allowed the identified issues of the previous project to be overcome:
1) Solving Speed – the solving speed of the heuristic is greatly improved over the optimisation model. Part of the problem with the optimisation model was the use of LP Solve, a free solver tool, which was quite slow in solving – taking up to one week to gain an optimal solution using the previous model. The heuristic is able to find a feasible schedule in three minutes for a 53-event season checking three resources. For most situations solving times of less than ten minutes are expected – useful if rescheduling is to be performed. This speed improvement does depend on the data and parameters used; however for most possibilities the heuristic solving time can be stated in minutes, rather than days like the optimisation model.
2) More Realistic Resource Treatment – the heuristic deals with all resources by daily allocations rather than as constant values over the duration of the event. This means that helicopter and fixed wing aircraft usage in an event can be attributed to each relevant day. This also means that the use of Scott Base beds can be varied over the length of an event to take account of time an event may be in the field or if the number of personnel in an event changes.
3) Greater Flexibility – the 2010 model only deals with creating an initial feasible schedule, meaning that once a schedule is created making changes to events or adding additional events, as well as changing the resource usages for which feasibility is desired, should be relatively easy without changing the overall outcome of the schedule too much. An optimisation model for the schedule, on the other hand, could result in extremely different outcomes if events are changed or added and it is run again. The new software has tools for changing or adding events in the schedule.
4) Greater Simplicity – the previous model required the user to manually load a file created by the Excel worksheet into the LP Solve problem, the output of which is then retrieved by the Excel workbook again. Our model deals with all the data input, heuristic processing and result output in the same workbook.
It is hoped that by endeavouring to overcome all of the identified limitations of the previous model that the new model created will more closely approximate the real world situation and will be of use and benefit to Antarctica NZ.
The model works by aiming to reduce the infeasibility of resource usage over the whole season. A feasible schedule is one that results in zero infeasibility of resources in the season.
The model begins by inserting the events into the schedule one by one into a best position relative to the events already entered. The best position is calculated by looking to reduce the infeasibility created by each event after it is entered into the schedule.
After this construction has been performed the resource usage of every day of the season is calculated. Where the resource usage of a day exceeds the resource capacity the infeasibility is weighted and recorded for that day. The improvement phase of the heuristic identifies the day in which the resource infeasibilities are greatest and identifies the events that are scheduled on that day. These events are then iteratively tested with movements within their possible travel window until an improvement in the season infeasibility is recorded. The event is then moved to the new time and the process is started again with the next most infeasible day.
This process runs until either a feasible solution is found or until the time ends. At this point the feasible solution (or least infeasible solution) is output into the results section. Infeasibilities in the resource usage are easily identified in the output by being highlighted with a red background on the corresponding days. This allows Antarctica NZ to make decisions on whether additional resources may need to be acquired for this period or whether another solution is available for them.
The feasible schedule model uses an Excel spreadsheet as an interface for the user to input data and separate worksheets for displaying the resulting event schedule and resource usages on a daily basis. The schedule is found using a heuristic coded in VBA and the resource usage calculated from the resulting schedule. The interface is separated into three parts; Event Requirements, Resources Used and Results.
The spreadsheet can be formatted with respect to the open season date, season duration, number of events and number of resources. The spreadsheet takes all the data entry from the user, therefore VBA commands are programmed to identify user data entry errors, such as specifying event travel windows outside of the season window and specifying event resource usage outside of the event duration, among others. Problems with data input are therefore identifiable and able to be corrected. There are additional commands in the worksheet that allow for input of event data and changing/removal of events. The search commands also make navigating the worksheet easier when adjusting and entering the data.
Figure 1, Event Requirement worksheet, for data entry.
The general nature of this input page means that if Antarctica NZ is worried about other scarce resources being in conflict between events they are able to add additional resources, such as generators or tents, and calculate a schedule to see how it may change or whether the resource really will present a problem. Currently existing events and resources can also be edited and deleted.
Resource capacities and weights are used to set the resource restrictions and identify their relative importance. A high ‘Resource Weight’ value means that the heuristic will work to reduce the infeasibility of that resource more than a less highly weighted resource. For example the helicopter resource weight of 3 will mean that the helicopter resource will be focussed on for feasibility by the heuristic more than the Hägglund resource, with its lower weighting of 0.2.
Figure 2, Resource parameters.
The ‘Flight Availability’ worksheet allows the user to specify the days that events are able to travel to Antarctica. This is a 0/1 variable with 0 meaning no flight and 1 meaning there is a flight on that day. The scheduling model will only allow events to start on a day that has an available flight. This allows Antarctica NZ to input their possible flight timetable and see how it affects the scheduling of the events for the season. Where they are trying to decide between two possible flight dates they could run the scheduling model twice, with the flight availability changed between the runs. This will allow them to see if one of the proposed dates may be better than the other in the resulting schedule or if either date is just as good.
Figure 3, Flight availability constraint.
After the heuristic finishes running it outputs the resulting feasible schedule (or the least infeasible schedule) into the ‘Gantt Chart’ worksheet. The cells will be highlighted black to indicate the position of the event within the open season. The start and finish dates of each event in the schedule are also shown.
Figure 4, Gantt chart of resulting schedule.
The ‘Resources Used’ worksheet will display the resources used on a daily basis after the heuristic has finished running.
Figure 5, Daily resource usage output.
The leftover available resources for each day are also displayed on this worksheet, shown in figure 6 in the green ‘Resource Slack’ columns. This allows for easy identification of where additional events may be scheduled or where demand for the resources may be tight. If no feasible schedule is found then the ‘Resources Used’ worksheet is where the infeasibilities can be identified. The resource(s) that are outside of their capacity are identified by a red background on the appropriate day.
Figure 6, Resource Used worksheet, showing resource daily resource usage and slack.
This project has been able to create a scheduling model that overcomes the limitations identified by Antarctica NZ in the previous model. It is hoped that the model is a realistic approximation of the real-world situation and will be of help for, and used by, Antarctica NZ. Testing of the model leads to the belief that this will be the case and that the model will save Antarctica NZ a lot of time and effort in their scheduling.
We would like to thank Greg Jack from Antarctica NZ for his help in clarifying the problem for us and in supplying all of the necessary data. He was also very helpful in critiquing our developed model and recommending changes that will make it more usable by Antarctica NZ.