17 Optimal Scheduling

1 Introduction

Industrial, financial, commercial or any kinds of activity have at least one common feature: the better organized they are, the higher the profit, the better the quality or the lower the cost. Everyone makes a schedule to organize his or her own life. Making a schedule for any organized activities, one considers a sequence of tasks and a list of resources. Resources include tools, machines, materials, work force e.t.c. Of course, making a schedule for organization is far more difficult than making a schedule for our everyday life.

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 $http://mockus.org/optimum$ and can be run by a standard browser with Java support.

2 Flow-Shop Problem

The flow-shop problem is a simple case of the large and important family of scheduling problems We denote the sets of jobs and machines by $J$ and $S$. Denote by $\tau_{j,s}$ the duration of operation $(j,s)$. Here $j \in J$ denotes a job and $s \in S$ denotes a machine.

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

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

1 Permutation Schedule

The number of feasible decisions for the flow-shop can be very large. One reduces this number, if one considers only the so-called permutation schedules that are subsets of all feasible schedules. The permutation schedule is a schedule with the same job order on all machines. Here one defines a permutation schedule by fixing a sequence of job indices, for example, $1,2,...,n$. The schedule is transformed by a single permutation of job indices. As usual, permutation schedules describe the optimal decision well and are easier to implement [Baker, 1974].

2 Heuristics

A simple priority rule is defined by the Longer-Job heuristics

$$\begin{eqnarray} h_i(j)= {\tau_j- A_i \over A^i- A_i } +a, \end{eqnarray}$$

were

$$\begin{eqnarray} A_i=\min_{j} \tau_j,\ A^i=\max_{j} \tau_j , \ a>0. \end{eqnarray}$$

Here

$$\tau_j=\sum_{s}\tau_{j,s}$$

where $\tau_j$ is the length of the job $j$.

3 Results

Table 17.1 illustrates results of Bayesian Heuristic Approach (BHA) [Mockus, 2000] after 100 iterations using the Longer-Job heuristic (17.1) and different randomization procedures. The objective is a stochastic function. This function defines the shortest make-span found after $K$ repetitions.

In the example, $J^*=S^*=O^*=10$, where $J^*,\ S^*,\ O^*$ 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.

Table 17.1: Results of BHA using Longer-Job Heuristics.

$R=100$, $K=1$, $J^*=10$, $S^*=10$, and $O^*=10$
Algorithm	$f_B$	$d_B$	$x_0$	$x_1$	$x_2$
BHA	6.183	0.133	0.283	0.451	0.266 CPLEX

In Table 17.1 the symbol $f_B$ denotes a mean, and $d_B$ denotes a standard deviation of the make-span.
"BHA" denotes the Bayesian Heuristic Approach optimizing a "mixture" of heuristic algorithms.
$x_0$ defines the optimal ratio of Monte Carlo heuristics (algorithm 0) meaning equal probabilities,
$x_1$ shows the optimal proportion of linear randomized heuristics (algorithm 1) where probabilities are proportional to heuristics $h_i$,
$x_2$ 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 $i=0,1,2$ with probabilities $x_i$. Second time, the randomization is to chose the next job using the algorithm $i$ selected in the first stage.
The objective is to minimize the average make-span that is a stochastic multi-modal function of variables $x_i,\ i=0,1,2$ 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.

Figure 17.1: Numerical results and convergence line, the 'FlowShop' task.

3 Traditional School Scheduling

School scheduling is an example of the general scheduling problem. We consider the case where the objective is the number of "empty" hours when the teachers wait for the next scheduled lectures. One calls these hours as "teacher gaps, " or just "gaps" for short. We search for such schedules that reduce the sum of teacher gaps considering the schedules of fifth to twelfth class of the public high school. Other factors are school-specific and should be included adapting the software to specific schools.

1 Constraints

There are five 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.

2 Data Structure

Figure 17.2 shows a fragment of the existing weakly schedule of some Lithuanian school.

Figure 17.2: Uploaded Schedule-Row Data

• the schedule is defined as a string array $Mokytojai [64][38]$,
• the string $Mokytojai [i][1]$ defines the name of the $i$-th teacher, for example, $O. Dilidaviciene$, $V. Vilkiene$, e.t.c.
• the string $Mokytojai [i][2]$ defines the subject of the $i$-th teacher, for example, $lietuviu\_k$ means Lithuanian, $rusu\_k$ means Russian, $anglu\_k$ means English, $matematika$ means Mathematics,
  $informatika$ means Informatics, e.t.c.
• the string $Mokytojai [i][3]$ defines the code of the classroom of the $i$-th teacher, for example, $0$ means no special study, $A$ means a study for Informatics, e.t.c.
• the sequence of strings $Mokytojai [i][j],\ j=4,...,38$ define the class codes of the $i$-th teacher for all weak, for example, in the class code $P19c$, the first symbol $P$ means Monday, the second symbol $1$ defines the first lesson, and the third symbol $9c$ means the class $9c$, teacher gaps are denoted by symbols $X$, symbols $Q$ denote "open" lessons, a lesson is called "open", if a teacher is free before or after this lesson.

3 Permutation and Evaluation Algorithm

The process of checking and correcting illustrate Figure 17.3.

Figure 17.3: Correcting "Double Lecture"

The corrected schedule is optimized using the permutation algorithm. The algorithm follows a general pattern of permutation algorithms related to the Bayesian Heuristic Approach [Mockus, 2000]

1. record the current schedule $Mokytojai0$
   by reading the data file $Mokytojai [64][38]$,
2. record the current number of teacher gaps,
3. set the initial iteration number $it=0$,
4. set the current iteration number $it:=it+1,\ it <K$,
5. if $it=K$, stop and print the current schedule,
6. set the initial teacher number $i=-1$,
7. set the current teacher number $i:=i+1$,
8. if $i >63$ go to the step 4,
9. generate uniformly distributed random number $\xi \in [0,1]$,
10. go to the step 7, if $\xi < x$,
11. select a gap of the teacher $i$,
    go to step 7, if there are no gaps,
12. select an open lesson of the $i$-th teacher,
    go to step 7, if there are no open lessons,
13. make a permutation by exchanging the "gap class" with the open one,
14. test the feasibility conditions listed in section 3.1,
    go to the step 16, if the permutation is feasible,
15. restore the feasibility by restoring the teacher gap and go to the step 7,
16. count the teacher gaps in the permuted schedule,
17. compare the number of the teacher gaps in the current schedule with the permuted one,
18. 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

The algorithm is very simple and natural. It mimics, in a sense, the usual ways to improve existing schedules. However, replacing a "gap" class by the open one, defined in the step thirteen, a new gap for another teacher is opened, as usual. The algorithm does not satisfy the convergence conditions [Mockus et al., 1997]. To satisfy these conditions the probability to reach any schedule should be positive.

4 Running Software

The GMJ1 and GMJ2 systems described in [Mockus, 2000] are used in [Perlibakas, 1999] for optimization of BHA parameters following these steps:

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

Figure 17.4: Fragment of the Optimized Schedule

To see the optimal schedule click the button $TvarkaAnalyser$ (see Figure 17.5).

Figure 17.5: Results of GMJ1.

The software is available at the web-site $http://mockus.org/optimum$, the section "Discrete Optimization", examples "School-COMPLETE" and can be run by a browser with Java support.

4 Profiled Schools

1 Introduction

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 $MIMOSA$. The $MIMOSA$ 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 $MIMOSA$ depends on the human scheduler operating $MIMOSA$ system. Therefore, comparison with other systems is very difficult. In this sense, the $MIMOSA$ 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 .

2 Schedule Representation

A way to define the complete schedule of profiled school is to represent it as a four-dimensional binary array

$$\begin{eqnarray} schedc[M][V][G][K]. \end{eqnarray}$$

Here
$M$ is a number of teachers,
$V$ denotes the total number of weekly working hours,
$G$ is a number of different interest groups,
$K$ is a number of school rooms,

$$\begin{eqnarray} schedc[i][j][k][l]=1 \end{eqnarray}$$

means that the teacher $i$ at the hour $j$ teaches the interest group $k$ in the class room $l$,

$$\begin{eqnarray} schedc[i][j][k][l]=0, \end{eqnarray}$$

means no lesson.

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

$$\begin{eqnarray} schedg[M][V][K]. \end{eqnarray}$$

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

$$\begin{eqnarray} schedg2[M][VK]. \end{eqnarray}$$

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

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

$$\begin{eqnarray} sched_k[M][V][K]. \end{eqnarray}$$

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

$$\begin{eqnarray} sched2_k[M][VK]. \end{eqnarray}$$

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.

3 Objective Function

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.

4 Normative Constraints

The standard restrictions are

1. for each group $k$ the total number of weekly hours $v_{sk} \le V_{sk} < 168$,
2. for each group $k$ the total number of daily hours $v_{dk} \le V_{dk} < 24$,
   for eleventh and twelfth grades $V_{sk} < 5 V_{sd}$,
   for the rest $V_{sk} = 5 V_{sd}$
3. for each teacher $i$ the total number of weekly hours is $V_{i}$,
4. for each group $k$ the total number of weekly hours for a subject $n$ is $V_{kn}$,
5. not more than one lesson at a time in a class ,
6. for some subjects and groups "double" lessons are needed,
7. for some subjects and groups "double" lessons are forbidden,
8. for some subjects and groups "double" lessons are allowed,
9. no gaps for students from the first to tenth grade.

5 Convenience Constraints

The usual factors of inconvenience are

1. teacher gaps
2. student gaps (for eleventh and twelfth grades)
3. inconvenient hours
4. inconvenient days
5. inconvenient sequences of lessons

6 Penalty Function

1 Normative Penalties

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

$$\begin{eqnarray} C_n=\sum_r c_r N_r \end{eqnarray}$$

where
$c_r$ is the penalty for violation of the normative $r$,
$N_r$ is the number of corresponding violations.
In this case $r=1,..,9$.
The actual numbers $c_r$ are expert estimates and depends on general situation of the school. Therefore, they are parameters defined by users using graphical interfaces, as usual.

2 Penalties of Inconvenience

Penalties of inconvenience are defined by users for each inconvenience factor:

1. $c_i$ is the penalty for the teacher $i$ gap,
2. $c_k$ is the penalty for the group $k$ gap,
3. $c_{ji}$ is the penalty of the hour $j$ that is inconvenient for the teacher $i$
4. $c_{li}$ is the penalty of the day $l$ that is inconvenient for the teacher $i$
5. $c_{jk}$ is the penalty of the hour $j$ that is inconvenient for the group $k$
6. $c_s$ is the penalty for inconvenient sequence $s$ of lessons,

The general inconvenience penalty

$$\begin{eqnarray} C_c=\sum_i c_i L_i + \sum_k c_k L_k+ \sum_i \sum_j c_{ji} L_i^... ...\sum_l c_{li} L_i^l + \sum_k \sum_j c_{jk} L_k^j + \sum_s c_s L_s \end{eqnarray}$$

where
$L_i$ is the number of gaps of teacher $i$,
$L_k$ is the number of gaps of group $k$,
$L_{i}^j$ is the number of hours $j$ that are inconvenient

for the teacher $i$,
$L_{i}^l$ is the number of days $l$ that are inconvenient for the teacher $i$,
$L_{k}^j$ is the number of hours that are inconvenient for

the group $k$,
$L_s$ is the number of inconvenient sequences of lessons.

The objective function is the total penalty

$$\begin{eqnarray} C=C_n+C_c \end{eqnarray}$$

Then the optimization problem is

$$\begin{eqnarray} \min_{\tau \in \Theta} C(\tau), \end{eqnarray}$$

where $C(\tau)$ is the total penalty of some schedule $\tau$,
$\Theta$ is the set of schedules satisfying the physical constraints. The penalties $C(\tau)$ depend on expert evaluations, therefore we regard them as heuristics.

7 Defining the Initial Schedule

In some cases the initial schedule is defined by users. Otherwise it is build by some greedy 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.

8 Optimization by Permutations

The initial schedule is improved by permutations. The best obtained schedule is recorded after each iteration. Changes to worse schedules are performed with some probabilities. That is for improving convergence conditions.

A natural first step while trying to provide convergence is the Simulated Annealing (SA):
One moves from the current schedule $i$ to the permuted schedule $i+1$ with probability

$$\begin{eqnarray} r_{i+1}&=&\cases {e^{{-h_{i+1} \over x /\ln (1+N)}}, &if $h_{i+1} > 0$, \cr 1, &otherwise.\cr} \end{eqnarray}$$

Here $N$ is the iteration number and $x$ is the "initial temperature." The logarithmic "cooling schedule" $\ln (1+N)$ follows from convergence conditions [Cohn and Fielding, 1999].

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

$$\begin{eqnarray} r_{i+1}&=&\cases {e^{{-h_{i+1} \over x_1 /\ln (1+x_2 N)}}, &if $h_{i+1} > 0$, \cr 1, &otherwise, \cr} \end{eqnarray}$$

where $x_1 \ge 0$ defines an "initial temperature" of SA and $x_s \ge 0$ describes its "cooling rate".

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

9 Software 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.

1 Applet version

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 $http://mockus.org/optimum$, enters the problem named "School-PROFILED" in the section "Discrete Optimization" and starts $applet.html$ by a browser that supports Java.

2 User Data

The data file defines the list of subjects and the students choices. File format is $txt$, one record isl for one subject.

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 $11$ denotes eleventh grade, the code $AngLg$ means the $Lg$ version of English, $ZenMar$ is the abbreviation of teacher name, $30$ is the classroom number, $3$ is the number of weekly lessons, $11LeonUla$ defines a name of student of eleventh grade, e.t.c.
A fragment of user data file is in Figure 17.6.

Figure 17.6: User Data

Figure 17.7 shows the opening window.

Figure 17.7: Opening Window

User data is uploaded by CGI interface clicking the $Browse$ button. The scheduling starts by the $Read\ data$ button.
User preferences are expressed defining restrictions and preferences and assigning penalty points for violating these restrictions and preferences.

3 Initial Schedule

The initial schedule is built by priority rules and randomization. For example, continuous lessions are included first, starting from Monday. Then all the lessions are listed that can be performed at the same time without violation of physical restrictions and day-off requests. One lession per day is scheduled. Both student and teacher gaps are ignored while building the initial schedule. The main difficulty is to list all the subjects without exceeding the default limit of 9 daily hours. To achieve this the random mixing of schedule lines is used up to 100 times. After that the limit is increased by 1 (first time from the default 9 to 10 hours per day). The initial schedule is completed by moving the largest classes to early hours.

4 Optimization by Permutations

First a window opens for starting optimization and defining randomization parameter $x$. The permutations are similar to those in traditional school. The difference is that both the teacher and the student gaps are considered and the probability $x$ to pass a person $i$ is fixed. This reduces optimization possibilities as compared with the traditional school scheduling software. Note that the advanced servlet version includes optimization of all the heuristic parameters.

5 Servlet versions

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.8: Opening the program.

Figure 17.9 shows how data is uploaded, preferences and restrictions defined.

Figure 17.9: Uploading data.

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 $9$ 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 $10$, the initial probability to "miss" a teacher is $0.5$, both the initial "temperature" $X1$ and the "cooling" rate $X2$ of SA are open.

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

Figure 17.10: Optimization window

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: $Mokyklos\ tvarkarastis$ means school schedule, $Pirmadienis$ is Monday, $Antradienis$ is Tuesday, $klaida$ means that user data is not correct here.

Figure 17.11: Optimized school schedule

The optimized schedule of teacher Jancius is in Figure 17.12.

Figure 17.12: Optimized schedule of teacher Jancius

The optimized schedule of student Butkus is in Figure 17.13

Figure 17.13: Optimized schedule of student Butkus

10 Conclusions

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.