Scheduling terminology differs widely between countries, between organisations within a single country, and even between parts of a single organisation. Hartley [2-16] has produced a glossary which includes alternative terms for the same concept, and alternative concepts for the same term. We attempt here while following Hartley to use terms which do not have alternative meanings and are easily understood. Thus, we use block to mean a sequence of trips assigned successively to one bus, beginning with a pull-out and ending with a pull-in. A bus which leaves the depot more than once in a day consists of several blocks. A shift is the work scheduled to be performed by a driver in one day.
The driver scheduling problem
The process of driver scheduling is the construction of a set of legal shifts (including overtime portions where allowed) which together cover all the blocks in a particular vehicle schedule, that is, in a schedule for several vehicles which may reflect the whole operation of an organisation, or a self-contained part of that operation. The problem is generally known as run-cutting in North America, and is often referred to as crew scheduling elsewhere. Blocks may be considered as being divided into units of work which start and finish at relief
- 1 -
opportunities when the vehicles pass agreed change-over points. Several successive units of a block may form a portion of a driver's shift, and a shift may cover portions of several blocks, although efficiency is often lost if drivers change blocks unnecessarily. Driver scheduling methodology is readily extensible to situations where more than one person is assigned to a vehicle; either the whole crew is subject to similar rules and may be scheduled together, or separate schedules are produced for different crew members.
Driver scheduling is subject to a set of rules which is specific to an organisation. These rules are generally mixtures of national and local rules, and some may be unwritten or may be soft rules which may be broken in some cases. Typically, there are restrictions on the total time worked, on the length of time that may be worked without a meal break, on the total spreadover (duration between beginning and end of a shift), etc..
The nature of the rules has a profound effect on the ease with which a schedule may be compiled by computer, and many relatively primitive systems which have been developed for particular circumstances cannot be applied to more severely constrained situations. Rules relating to the position of a meal break within a shift are noteworthy in this respect. In general, both manual schedulers and computer systems find it more difficult to compile efficient shifts where the maximum time that may be worked without a break is short, although the existence of a tight constraint on this time may help certain scheduling systems by reducing the number of potential legal shifts.
Most developed countries have labour laws which require a meal break after a maximum period of between four-and-a-half and five-and-a-half hours. However, the European Community has a complex set of rules which provide for either a single break (of 30 minutes) or two shorter breaks, or three yet shorter breaks, or a shift with no formal breaks, provided the cumulative slack time between journeys satisifies certain requirements. Despite this, many, if not most, bus companies in Europe obey local rules stipulating the provision of a meal break. The major computer scheduling systems necessarily therefore incorporate sophisticated techniques designed to ensure efficient provision of breaks.