BE Seminar

Introduction to the algorithm behind the "Supercycle Optimiser"

by Sandy Easton (CERN)



The "Supercycle Optimiser" is a Java program to automate and optimise the scheduling of beams passing through the CERN injector complex.

The program is an implementation of the "Terrapin" algorithm, which was created at CERN. It is able to perform an exhaustive search on the space of possible schedules for a set of beams requested by our users, and outputs an unbeatably efficient and truly optimal schedule which obeys any inter-beam scheduling constraints that were defined.

Other existing scheduling algorithms which could attempt the same task are typically heuristic and inexhaustive, and thereby their solutions can only be treated as a good guess at the optimal solution. Hence, the Terrapin algorithm is specially strong, while still maintaining a practical runtime.

In this introductory seminar, we will limit ourselves to scheduling a single, uncoupled accelerator, and explore how the entire schedule-space can be searched for maximally efficient solutions, without performing a brute-force.

We will also examine how the hardware/user constraints which affect scheduling decisions in the injector complex can be readily obeyed by the algorithm.

The seminar will consist of a presentation (1 hour) followed by an open discussion. Worked examples and some exercises (with solutions) will be available afterwards for those interested.

Scheduling for all the whole injector chain at once ("parallel scheduling") is an extension of the concepts to be presented here, and will itself be the subject of a second seminar at a later date.

N.B. This seminar will not feature a demonstration of the "Supercycle Optimiser" program, since this would not add any technical understanding of the algorithm itself. Anyone interested in such a demonstration should contact the organiser separately.

Organized by

Sandy Easton

Videoconference Rooms
Virtual auditorium. Pets are welcome, but smoking is not permitted.
Sandy Easton
Auto-join URL
Useful links
Phone numbers