- 1 Introduction
- 2 Flow-Shop
Problem

- 3 Traditional School Scheduling

- 4 Profiled Schools

17 Optimal Scheduling

A failure to make a schedule or devising a wrong schedule can result in delay of a deadline and can cost much of the money [Ahuja et al., 1994,Hajdu, 1997].

First we consider a simple flow-shop scheduling problem. Here the sequence of tools is fixed by technology. One minimizes the make-span, which is the time from the beginning of the first task until the end of the last one. That is a well known simplest model presented just to illustrate how the Bayesian Heuristic Approach (BHA) [Mockus, 2000] could be applied in scheduling problems.

The second example is scheduling of traditional school that is closer to real life tasks. Here the sequence of teaching subjects, regarded as tools, can be changed. One needs to reduce the sum of gaps ("empty" hours) in the teacher schedules. There should be no gaps for students. Different classes are considered as different tasks. The classrooms, including the computer and physics rooms and studies, are the limited resources.

The most difficult example is scheduling of profiled school. Here eleventh and twelfth grade students are choosing , for example, 14 subjects from 64. This means that each student works by his own schedule. We search for the most convenient feasible schedule. The inconveniences are evaluated by penalty points.

All the software is available at the web-site and can be run by a standard browser with Java support.

2 Flow-Shop Problem

Suppose that the sequence of machines is fixed for each job . One machine can do only one job at a time. Several machines cannot do the same job at the same moment.

The objective function is the make-span , the time to complete all the jobs.

1 Permutation Schedule

2 Heuristics

were

Here

where is the length of the job .

In the example,
, where
are numbers of
jobs, machines, and operations, respectively. Lengths and
sequences of operations are generated as random numbers uniformly
distributed from zero to ninety-nine. The expectations and
standard deviations are estimated by repeating forty times the
optimization of a randomly generated problem.

, , , , and | |||||

Algorithm | |||||

BHA | 6.183 | 0.133 | 0.283 | 0.451 | 0.266 CPLEX |

"BHA" denotes the Bayesian Heuristic Approach optimizing a "mixture" of heuristic algorithms.

defines the optimal ratio of Monte Carlo heuristics (algorithm 0) meaning equal probabilities,

shows the optimal proportion of linear randomized heuristics (algorithm 1) where probabilities are proportional to heuristics ,

is the optimal ratio of greedy heuristics (algorithm 2) when one selects the longest available job.

Note that randomization is applied in two stages. First time the randomization is to select the algorithm with probabilities . Second time, the randomization is to chose the next job using the algorithm selected in the first stage.

The objective is to minimize the average make-span that is a stochastic multi-modal function of variables therefore, the Bayesian search is applied [Mockus, 2000]. This explains the term Bayesian Heuristic Approach (BHA).

"CPLEX" denotes the the well known general discrete optimization software after twenty hundred iterations (one CPLEX iteration is comparable to a Bayesian observation). Weak results of CPLEX show that the standard MILP technique is not efficient in solving this specific problem of discrete optimization. It is not yet clear how much one improves the results using specifically tailored B&B.

To optimize BHA parameters for a given Flow-Shop problem, one applies the Java optimization system GMJ2 that reduce the average deviation [Greicius and Luksys, 1999].

The optimal proportions of three heuristics: the Monte Carlo, the linear randomization and the "Select-the-Best" are on the output page (see Figure 17.1). The convergence line is there, too. These are results of one hundred iterations by the 'Bayes' method.

3 Traditional School Scheduling

1 Constraints

- at any given moment a teacher can deliver only one lesson,
- at any given moment a student can take part at only one lesson,
- no "student gaps"are allowed,
- the "double" lectures (the sequence of two lectures of the same subject) are not allowed (there are some exceptions),
- the number of lecture hours per day is limited.

- the schedule is defined as a string array ,
- the string defines the name of the -th teacher, for example, , , e.t.c.
- the string
defines
the subject of the -th teacher, for example,
means Lithuanian, means Russian, means
English, means Mathematics,

means Informatics, e.t.c. - the string defines the code of the classroom of the -th teacher, for example, means no special study, means a study for Informatics, e.t.c.
- the sequence of strings
define the class codes of the -th teacher for
all weak, for example, in the class code , the first symbol
means Monday
^{}, the second symbol defines the first lesson, and the third symbol means the class , teacher gaps are denoted by symbols , symbols denote "open" lessons, a lesson is called "open", if a teacher is free before or after this lesson.

- record the current schedule

by reading the data file , - record the current number
of teacher gaps
^{}, - set the initial iteration number ,
- set the current iteration number ,
- if , stop and print the current schedule,
- set the initial teacher number ,
- set the current teacher number ,
- if go to the step 4,
- generate uniformly distributed random number ,
- go to the step 7, if ,
- select a gap of the teacher
,

go to step 7, if there are no gaps, - select an open lesson of the -th teacher,

go to step 7, if there are no open lessons, - make a permutation by
exchanging the "gap class"
^{}with the open one^{}, - test the feasibility conditions listed in section 3.1,

go to the step 16, if the permutation is feasible, - restore the feasibility by restoring the teacher gap and go to the step 7,
- count the teacher gaps in the permuted schedule,
- compare the number of the teacher gaps in the current schedule with the permuted one,
- replace the current schedule
by the permuted one,

if the current number of teacher gaps is less then that in the permuted schedule,

go to step 7

- select the method and its parameters,
- select the task 'Tvarka' and its parameters including the iteration number , the lower and upper bounds for the randomization parameter , the default value of .

The algorithm described in the previous section is for scheduling of traditional schools. In these schools the study schedules are fixed for each grade.

Application of this algorithm is more difficult, if classes are divided depending on subjects of choice. For example, some students may choose religion, some others ethics, e.t.c. Here the number of "classes" is greater because the schedules of divided classes of the same grade are different. In addition, classes are divided for some subjects and united for others, as usual.

In so-called "Profiled Schools" the students of eleventh and twelfth year select, for example, fourteen subjects from sixty available. That means different individual schedules for most of the students. There are no stable student classes anymore. They are replaced by changing "interest groups". The changes happen each hour.

Personal choices of eleventh and twelfth grade students are defined as sets of subjects. Sequences of these subjects and the corresponding class-rooms are defined by the general school schedule.

In this case a new approach is needed for optimal scheduling. An example is the commercial system . The helps to produce feasible schedules by performing corrections, for example, by closing some gaps, and informing about violated constraints and inconveniences. About 50% of the schedules produced by depends on the human scheduler operating system. Therefore, comparison with other systems is very difficult. In this sense, the and other similar systems can be regarded mainly as "Support Systems."

The objective of this research is to design workable
optimization system for profiled school scheduling.
In the genuine optimization system a human operator
specifies just general objectives and constraints.
The schedules, both general and personal, are produced
automatically by an
optimization system. These schedules may be corrected by
an operator considering some additional factors not included
in
the general objectives and constraints.
The human operator can influence the outcome of optimization
by choosing an initial schedules, too
^{}.

Here

is a number of teachers

denotes the total number of weekly working hours,

is a number of different interest groups,

is a number of school rooms,

means that the teacher at the hour teaches the interest group in the class room ,

means no lesson.

The general schedule is represented as an three-dimensional binary array

To represent the general schedule in two dimensions the two-dimensional array is used

where is a string defining both the hour and the class room (see for example 17.2).

Personal schedules are defined for each interest group as three-dimensional binary arrays

To represent this schedule in two dimensions the two-dimensional array is used

The binary representation is simple and convenient for understanding and defining constraints but requires large memory and is not convenient for schedules of real profiled schools.

There are no schedules that satisfy all restrictions and personal preferences because they contradict each other as usual. For example, the ministry of education defines a number of rules to be observed, the school teachers and students both prefer schedules without gaps, etc. Thus, the objective is to find the best compromise of conflicting interests.

A compromise solution is reached by defining penalties
for violation of constraints and disregarding
inconveniences.
We search for such schedule that
minimizes the total penalty function. Only the "physical"
constraint may not be violated:

a person cannot be in two places at the same time.

We assume, that all other constraints may be violated, at a
price.
Both normative and convenience constraints are considered
in this research.

The standard restrictions are

- for each group the total number of weekly hours ,
- for each group the total number of daily hours
,

for eleventh and twelfth grades ,

for the rest - for each teacher the total number of weekly hours is ,
- for each group the total number of weekly hours for a
subject
^{}is , - not more than one lesson at a time in a class
^{}, - for some subjects and groups "double" lessons
^{}are needed, - for some subjects and groups "double" lessons are forbidden,
- for some subjects and groups "double" lessons are allowed,
- no gaps for students from the first to tenth grade.

The usual factors of inconvenience are

- teacher gaps
- student gaps (for eleventh and twelfth grades)
- inconvenient hours
- inconvenient days
- inconvenient sequences of lessons

Formally, the normative constraints cannot be violated. Practically, some minor violations could be tolerated, if this improves other parameters considerably. Thus the normative penalties must be high.

where

is the penalty for violation of the normative ,

is the number of corresponding violations.

In this case .

The actual numbers are expert estimates and depends on general situation of the school. Therefore, they are parameters defined by users using graphical interfaces, as usual.

- is the penalty for the teacher gap,
- is the penalty for the group gap,
- is the penalty of the hour that is inconvenient for the teacher
- is the penalty of the day that is inconvenient for the teacher
- is the penalty of the hour that is inconvenient for the group
- is the penalty for inconvenient sequence of lessons,

where

is the number of gaps of teacher ,

is the number of gaps of group ,

is the number of hours that are inconvenient

for the teacher ,

is the number of days that are inconvenient
for the teacher ,

is the number of hours that are inconvenient for

the group ,

is the number of inconvenient sequences of lessons.

The objective function is the total penalty

Then the optimization problem is

where is the total penalty of some schedule ,

is the set of schedules satisfying the physical constraints. The penalties depend on expert evaluations, therefore we regard them as heuristics.

Using the Greedy Heuristics techniques one builds the schedule from scratch. Here the results depend on the sequence of "building" operations. This way, one obtains a schedule that is convenient for the

first teacher but may be very inconvenient for the last teacher, e.t.c.

As usual, greedy heuristics define priorities. That means that subjects, classes and persons that are higher on the priority list obtain better schedules. The schedule build by pure greedy heuristics often does not satisfy some important restrictions. Therefore randomization is introduced. It helps to build better initial schedule by random mixing of schedule lines and so extending the range of search.

A natural first step while trying to provide convergence
is the Simulated Annealing (SA):

One moves from the current schedule
to the permuted schedule
with probability

Here is the iteration number and is the "initial temperature." The logarithmic "cooling schedule" follows from convergence conditions [Cohn and Fielding, 1999].

The difference from the traditional SA is that we optimize the parameter for some fixed number of iterations . In this case the cooling schedule should be optimized, too. A natural way to do it is by introducing the second parameter . This transforms expression (17.14)

where defines an "initial temperature" of SA and describes its "cooling rate".

SA and other discrete optimization techniques are explained in [Mockus, 2000] by the Knapsack example .

The profiled school scheduling software implements permutations similar to these of the traditional school considered in [Mockus, 2000]. That is only similarity. Important new ideas are developed and implemented while considering profiled school scheduling.

The fist one is that the schedule should be evaluated including both objective and subjective factors in a balanced way. The theoretical framework of this is the Pareto optimum. Simlest way to obtain Pareto optimal schedule is by assigning some penalty points for deviations from the desirable or feasible conditions. The total penalty is minimized. In such a case the penalty points represent subjective opinion of people responsible for schedules. The conditions reflects objective legal and physical factors.

The second new idea is optimization of heuristics by selecting their best parameters. That is achieved in three stages. In the first stage the same trivial permutation heuristics is used as in the traditional schedule. That works if one starts from nearly optimal schedule what is true in traditional schools as usual. In the profiled schools some "globalization" of permutation heuristics is needed.

That is achieved in the second stage by Simulated Annealing (SA) schedules applied with same fixed parameters such as initial "temperature" and the "cooling" rate The third fixed parameter is the probability to "miss" some teacher waiting in the "improvement" queue. In this case one accepts with some small probability schedules with higher penalties so improving convergence. It is easy to notice that the results of SA depend on all of three arbitrarily fixed parameters.

In the third stage these parameters are optimized using methods of stochastic global optimization developed in the framework of the Bayesian Heuristic Approach (BHA) [Mockus, 2000]. Each stage can be involved separately, that makes comparisons of their results much simpler.

There are two software versions: applet and servlet. The graphics of the applet version look better as usual, because graphical programs run at the user site. The servlet version runs using server resources. That is an advantage if user computing resources are limited.

This version implements only the first stage where the total penalty function is minimized locally using the simplest permutation heuristics That improves the initial schedules as usual. The advanced SA and BHA methods are implemented in the servlet version because servlet mode is more convenient providing schools with servers computing resources and better facilities for data exchange.

To run the applet one visits the web-site , enters the problem named "School-PROFILED" in the section "Discrete Optimization" and starts by a browser that supports Java.

Structure of the record is as follows:

1. Number of grade.

2. Subject code.

3. Teacher code.

4. Number of classrooms.

5. Number of classes per week.

6. List of attending students.

Records are not longer then 11 symbols. Fields are separated by the symbol |. The end of the line is marked by the symbol |^ For example, 11AngLg | ZenMar | 30 | 3 | 11LeonUla | 11KuprMin |^ 12MatLg | BirCer | 21 | 4 | 12GerdAbis | 12GirdSaru | 12GedLag |^Here the number denotes eleventh grade, the code means the version of English, is the abbreviation of teacher name, is the classroom number, is the number of weekly lessons, defines a name of student of eleventh grade, e.t.c.

A fragment of user data file is in Figure 17.6.

Figure 17.7 shows the opening window.

User data is uploaded by CGI interface clicking the button. The scheduling starts by the button.

User preferences are expressed defining restrictions and preferences and assigning penalty points for violating these restrictions and preferences.

There are three servlet versions. The simplest one is direct implementation of the applet version. The updated version adds optimization of heuristics by Simulated Annealing (SA) with fixed parameters. The advanced servlet version optimizes parameters of SA completing software implementation of the main theoretical ideas of the Bayesian Heuristic Approach (BHA) (see Figure 17.8).

Figure 17.9 shows how data is uploaded, preferences and restrictions defined. In the upper-left corner is a list of topics. Marking some of them introduces "double time" preferences. Important restriction is maximal number of hours per day. The default value is shown. Clicking "teacher list" one introduces teacher "days-off" requests.In the upper-right corner penalty points are defined. That is the subjective part of scheduling defined by persons responsible for scheduling reflecting informal local conditions and preferences.

The upper window in Figure 17.10 is for defining optimization parameters. Here the number of iterations is , the initial probability to "miss" a teacher is , both the initial "temperature" and the "cooling" rate of SA are open.

The middle window shows the difference between the initial schedule ( penalty points) and the optimized one ( penalty points). To see the complete schedules one clicks on corresponding words shown in the lower window of Figure 17.10.

The initial school schedule is in the lower part of Figure 17.9. The optimized school schedule is in Figure 17.11.Most of notations are similar to those in the user data. There are some Lithuanian terms: means school schedule, is Monday, is Tuesday, means that user data is not correct here.

The optimized schedule of teacher Jancius is in Figure 17.12. The optimized schedule of student Butkus is in Figure 17.13

The profiled school scheduling algorithms and software implements permutations similar to these of the traditional school considered in [Mockus, 2000]. That is only similarity. Important new ideas are developed and implemented considering profiled school scheduling.

The fist one is that the schedules should be evaluated including both objective and subjective factors in a balanced way. The theoretical framework of this is the Pareto optimum. Simlest way to obtain Pareto optimal schedule is by assigning some penalty points for deviations from the desirable or feasible conditions. The total penalty is minimized. In such a case the penalty points represent subjective opinion of people responsible for schedules. Desirable and feasible conditions reflects objective legal and physical factors.

The second new idea is optimization of heuristics by selecting their best parameters. That is achieved in three stages. In the first stage the same trivial permutation heuristics is used as in the traditional schedule. That works if one starts from nearly optimal schedule what is true in traditional schools as usual. In the profiled schools some "globalization" of permutation heuristics is needed.

That is achieved in the second stage by the Simulated Annealing (SA) schedules applied with same fixed parameters such as initial "temperature" and the "cooling" rate The third fixed parameter is the probability to delete the name of some teacher waiting in the "improvement" queue. In this case one accepts with some small probability schedules with higher penalties so improving convergence. It is easy to notice that the results of SA approach depend on all of three arbitrarily fixed parameters.

In the final stage these parameters are optimized using methods of stochastic global optimization developed in the framework of the Bayesian Heuristic Approach (BHA) [Mockus, 2000].

Each stage can be involved separately, that makes comparison of their results much simpler. Java implementation presents excellent opportunities to compare different scheduling versions for any interested person. The minimal user guide type information is presented in this paper to make easy the task of testing and applying the presented scheduling models.

The first few trials did show the better results as compared with the commercial software "MIMOSA" that now is used while scheduling Lithuanian profiled schools. However the statistical analysis of different school scheduling methods, algorithms and software systems is a separate important problem to be considered in future.

jonas mockus 2004-03-20