Development and evaluation of a scheduling algorithm for parallel hardware tests at CERN

This thesis aims at describing the problem of scheduling, evaluating different scheduling algorithms and comparing them with each other as well as with the current prototype solution. The implementation of the final solution will be delineated, as will the design considerations that led to it. The CERN Large Hadron Collider (LHC) has to deal with unprecedented stored energy, both in its particle beams and its superconducting magnet circuits. This energy could result in major equipment damage and downtime if it is not properly extracted from the machine. Before commissioning the machine with the particle beam, several thousands of tests have to be executed, analyzed and tracked to assess the proper functioning of the equipment and protection systems. These tests access the accelerator's equipment in order to verify the correct behavior of all systems, such as magnets, power converters and interlock controllers. A test could, for example, ramp the magnet to a certain energy level and then provoke an emergency energy extraction by one of the magnet controllers. Each test blocks the tested system for the duration of the test, which can take up to several hours. For safety reasons, the first tests in a system are always the ones with a lower risk of damaging the equipment, e.g. tests that work with low energy levels in the magnets. As soon as these tests have been analyzed and are considered successful, tests with higher risks are allowed to be executed. To minimize commissioning time and human error in test execution and result verification, a high degree of automation is essential. To achieve this, a new test tracking and execution framework has been developed at CERN, whose central point is a specialized scheduling strategy that decides which test should be executed when. This strategy has to meet certain requirements. For instance, it needs to consider test dependencies, parallel test execution and environment restrictions including equipment nonconformities or work on the equipment under test. For safety reasons, a high degree of dependability is another principal requirement for this component. Scheduling tests with constraints is a complex problem, and there are many different algorithms to solve it. The challenge of this thesis is not only to implement one of these algorithms but also to make this implementation easy to use, maintainable and reliable.