Information Operator Scheduling by Genetic
Algorithms
Takeshi Yamada, Kazuyuki Yoshimura, and Ryohei Nakano
NTT Communication Science Laboratories,
2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-0237, Japan{yamada, kazuyuki, nakano}@cslab.kecl.ntt.co.jp
http://www.kecl.ntt.co.jp/as

Abstract. In this paper, we discuss an approach to an operator scheduling problem in a large organization over time with the aim of maintaining service quality and reducing total labor costs. We propose a genetic
algorithm (GA) with a parameterized fitness function inspired by homotopy methods and with null mutation to handle a variable numberof operators. The proposed method is applied to the practical problemof scheduling operators in a telephone information center. Experimental
results show that the proposed method performs consistently better thana GA method previously developed.

1

Introduction

In the operator scheduling problem for customer service operations at a telephone information center, we are given a set of working shifts with known startand end times and number of short breaks to be taken during the work session.
The primary objective is to minimize staff shortages against number of customer
calls over time. This objective is so important to maintain service quality that
it is treated as a constraint such that the shortage must be zero. The secondary
objective is to minimize labor costs or a surplus of operators for actual needs.
Other objectives such as overtime and employee satisfaction are not considered.
This problem reflects the very significant needs of a large organization such as
an information service center for telephone directory assistance. Constructing agood schedule by hand, however, can be very difficult. Nippon Telegraph andTelephone Corporation (NTT), for example, has more than one hundred such
centers all over Japan and currently suffers huge deficits. There is urgent demand to automatically supply efficient schedules in a short time corresponding
to frequently changing work shift patterns and distribution of customer calls.
Genetic algorithms (GAs) have been successfully applied to a variety ofscheduling problems including jobshop and flowshop [2, 7, 4, 6, 8]. Yoshimura
and Nakano [9] first applied GAs to the information operator scheduling problem. They proposed a GA with mutation especially dedicated to the problem
and a partial reinitialization method with good success. The more general formof the problem is discussed in [3] under the name of the employee scheduling80

Number of Operators

70

n1 (t)n2 (t)

60
50
40
30
20
10

0
1
(8:00~8:05)

Time ( 5 min. units )180(22:55~23:00)

Fig. 1. Time distribution of required information operators

problem, where they proposed tabu search approach to solve the problem andcompared with other methods.
The organization of this paper is as follows. Section 2 explains the information
operator scheduling problem and its objective functions. In Section 3, we briefly
review the GA approach previously proposed by Yoshimura and Nakano [9]and then modify their mutation to handle a variable number of operators. In
Section 3.4 a GA with ranking based selection, duplicate elimination and local
search is proposed. A new approach using a parameterized fitness function is
proposed in Section 4. Experimental results using real data supplied by NTT
are reported in Section 5.

2

The Information Operator Scheduling Problem

The number of human operators required to deal with inquiry calls from customers changes over time, and its time distribution is given based on statistical
data at each center. Figure 1 shows such an example sampled at one of NTT’slargest centers. The service starts at t = 8:00 and ends at t = 23:00. The timeinterval is measured in units of five minutes, therefore the total service time interval of 15 hours corresponds to T = 180 time units. The vertical axis represents
the number of required operators for each time unit and is denoted by n1 (t). A
solid line at the top of the n1 (t) histogram represents tolerable surplus n2 (t): an
acceptable margin of at most 5 % at each time unit to absorb daily fluctuations.
A shift type specifies the work starting and ending times and the number ofbreaks to be taken during the work session. The number of breaks depends on
the length of the shift type, and the length of one break is fixed at 10 minutes (=2 time units). A break pattern is a placement of breaks under a given shift type.
A working pattern of an operator can be represented by specifying its shift typeand break pattern. An operator can choose any shift type from a list of admissible
shift types and any break pattern under the constraint that the length of any

Table 1. List of admissible working shift types
No.
Shift Type
Breaks No.
Shift Type
Breaks1
8 : 00 ∼ 12 : 00
4
9 14 : 00 ∼ 18 : 00
42
8 : 30 ∼ 12 : 00
3
10 14 : 00 ∼ 19 : 00
53
8 : 30 ∼ 12 : 30
4
11 17 : 00 ∼ 20 : 00
3
4
8 : 30 ∼ 13 : 00
4
12 17 : 00 ∼ 21 : 00
45
9 : 00 ∼ 13 : 00
4
13 17 : 30 ∼ 22 : 00
46
9 : 00 ∼ 14 : 00
5
14 17 : 30 ∼ 23 : 00
5
7 13 : 00 ∼ 17 : 00
4
15 19 : 00 ∼ 23 : 00
4
8 13 : 00 ∼ 17 : 30
4continuous working period must be between 30 and 60 minutes. Table 1 shows
an example set of admissible shift types and the number of breaks. For example,
a shift type with starting time 8:00 and ending time 12 : 00 has four breaks.
Let us assume there are a total of D operators available per day, and each ofthese operators is assigned a shift type selected from Table 1 and a break pattern.
A schedule is obtained by finding a combination of D working patterns withpossibly different shift types and break patterns. Each chosen working patterncorresponds to a (partial) schedule of one operator. Please note that even though
the total number D is fixed, the total labor costs differ depending on the total
length of the chosen shift types. In a center, operators must work in pairs, thus
a working pattern is shared by two operators. To avoid confusion, however, we
simply assume that one working pattern corresponds to one operator.
Let n(t) be a number of operators working at time t under a schedule S.
Total shortage of operators f1 and total surplus f2 are defined in Equation (1),where bxc = x if x > 0; otherwise bxc = 0.
f1 =

T
X

bn1 (t) − n(t)c,

f2 =

t=1

T
X

bn(t) − n2 (t)c.

(1)

t=1

The objective of the information operator scheduling problem is to minimize f2
under the constraint that f1 must be zero. In [9], a single f with a constanta ∈ [0, 1] in Equation (2) is used as a fitness measure. Another type of fitness
function shown in Equation (3) can also be considered where the constant α
must be small enough to satisfy f1 = 0.
f=

fα =

1−a
a
+
f1 + 1 f2 + 1

1,
1 + Fα(0 ≤ a ≤ 1).

F α = f1 + αf2(0 ≤ α ≤ 1).

(2)

(3)

3

Genetic Algorithms

3.1

Solution representations

A schedule S consists of a set of partial schedules of all the operators and isdenoted by S = {s1 , s2 , . . . , sD }. Each partial schedule si is a working patternof an operator and is represented by a string of 10 integer-valued genes as si =a1 a2 . . . a10 , where a10 represents its shift type number given in Table 1 and a9
the number of breaks, whereas a1 a2 . . . a8 represent continuous working length
before and after the breaks, thus a break pattern altogether. Each a1 a2 . . . a8
must be between 30 (= 6 time units) and 60 minutes (= 12 time units) as
described in Section 2, and only a1 , . . . , am (m = a9 + 1 ≤ 8) is actually used.
For example, an operator who starts working at time ts and ends at te as specified
by a shift type a10 , first works for a duration specified by a1 , then takes the firstten-minute (= 2 time units) break, and resumes work for a duration specified by
a2 and so on. The following equality must be satisfied (for more details, pleaserefer to [9]):ts + a1 + 2 + a2 + 2 + . . . + am = te (6 ≤ aj ≤ 12, m = a9 + 1).
3.2

(4)

Mutation

For each si probabilistically selected for mutation with probability pmut , oneof the following M1 to M4 is applied with the probabilities p1 , p2 , p3 and p4(p1 + p2 + p3 + p4 = 1), respectively.
M1 Two genes aj1 and aj2 are randomly selected and their values are exchanged.
M2 A gene aj1 with a value greater than 30 minutes is randomly selected anddecreased by 5 minutes, another gene aj2 with a value smaller than 60 minutes is randomly selected and increased by 5 minutes.
M3 a1 , . . . , am are randomly regenerated under the constraint Equation (4),while a9 and a10 remain the same.
M4 a10 is probabilistically changed to the next (a10 +1) or the previous (a10 −1)
type in Table 1, a9 to the corresponding number of breaks, and then a1 , . . .,am are randomly generated with the new a9 , a10 under Equation (4).
The mutation defined above assumes the number of genes and the total
number of operators D are fixed. However, it is desirable to extend the mutation
to allow D to be varied within an upperbound D0 during the search to find asolution of higher quality. A special gene null for a10 , meaning that the operator
is off duty, is introduced for this purpose. The following mutation M5, callednull mutation, is applied with probability p5 .
M5 (null mutation) : a10 is probabilistically changed to null.
The mutation M4 is slightly modified to incorporate this change such that if
a10 is null, it is changed to any type in Table 1 at random.

1. Initialize population: randomly generate a set of P schedules.
2. Repeat Step 2a to Step 2d L1 times:(a) Select two schedules S1 , S2 from the population with probabilities inversely proportional to their fitness ranks.
(b) Apply crossover with probability pcross and obtain T1 and T2 , otherwise
just copy S1 and S2 to T1 and T2 .
(c) For i = 1, 2, repeat as follows L2 times:
Apply mutation to Ti and obtain Ti . If Ti is at least as good as Ti , replace
Ti with Ti .
(d) For i = 1, 2, if Ti is better than the worst in the population, and nomember of the current population has the same fitness as Ti , replace theworst individual with Ti .
3. Output the best member in the population and terminate.

Fig. 2. Genetic local search for information operator scheduling problem

3.3

Crossover

A partial schedule-wise uniform crossover is employed as follows. Let two parent solutions be S1 = {s11 , s12 , . . . , s1m } and S2 = {s21 , s22 , . . . , s2m }. Before
applying crossover to S1 and S2 , their partial schedules sij are sorted first by
a10 and then by a1 , . . . , am in the case of ties. Let us denote the results by
Si = s∗i1 s∗i2 . . . s∗im (i = 1, 2). A new schedule T1 is generated by selecting s∗1j ors∗2j randomly for each j (1 ≤ j ≤ m). Similarly T2 is generated by selecting as∗ij for each j that is not selected for T1 .
3.4

Genetic local search

It is well known that there are some problem classes in which GAs are not well
suited for fine-tuning structures that are very close to optimal solutions andthat it is essential to incorporate local search methods into GAs. The resultof such incorporation is often called Genetic Local Search (GLS) [5]. In thisframework, an offspring obtained by a recombination operator is not includedin the next generation directly but is used as a “seed” for the subsequent local
search. The local search moves the offspring from its initial point to the nearest
locally optimal point, which is included in the next generation.
The mutation discussed in Section 3.2 is used for local search here. Instead of
applying mutation only once to each individual generated from the crossover, it
is applied repeatedly and the results are accepted only when they are improved(or at least the same). Figure 2 shows the outline of our GLS algorithm basedon the steady state model with ranking selection. The reinitialization method
introduced in [9] is substituted by the duplicate elimination technique in Step 2d
to avoid premature convergence even under a small-population condition.

Table 2. Performance comparison under various parameter conditions
No.
I
II
III
IV
V
VI

4

parameters
fitnessD
f in [9]
105
f α=1
105
f α:1→0105
f α:1→0100
f α:1→0≤ 120
f α:1→0≤ 105

f1 (avg.)
0
9.7
0
3.0
0
0

results
f2 (avg.)
f2 (best)
173.5
135
118.1
143.1
123
102.5
128.7
107
119.9
97

D(avg.)
103.2
102.8

Parameterized Fitness Function

Yoshimura and Nakano use f in Equation (2) with a = 0.7 as a fitness function [9]. They observe that their GA finds a solution with f1 = 0 effectively
as long as a > 0.3, while the quality of f2 is not always excellent. In their experiments, f1 and f2 start from large values, then f1 quickly decreases to zeroand does not increase again, while f2 decreases very slowly. Once a solution S
with f1 (S) = 0 is found, a new solution S 0 with f1 (S 0 ) > 0 is difficult to survive
because f (S 0 ) is inferior to f (S) in many cases. Thus only a limited region where
f1 is always 0 is searched. On the other hand, if f α with α = 1 in Equation (3)is used, both f 1 and f2 decrease smoothly, but f1 does not reach zero or close
to zero. One may be able to overcome this dilemma by finding an optimal α inEquation (3), but this itself is quite difficult.
As a possible remedy, we treat α as a parameter, which decreases from 1 to
0 throughout the search. For our purpose, the algorithm in Figure 2 is slightly
modified to use the parameterized f α in which α is first initialized as α = 1 in
Step 1, and is changed as α := (1 − )α in Step 2b after the crossover is applied,
where  > 0 is a small constant.
The idea of a parameterized fitness function is inspired by a far more sophisticated approach known as the homotopy method, which has been used for
decades to find solutions of nonlinear equations [1]. By initializing α = 1, westart from a relaxed problem in which minimizing f2 is easier at the cost ofviolating the constraint f1 = 0. α is then gradually decreased to enforce f1 = 0
and finally a schedule with f1 = 0 and reasonably small f2 is obtained.

5

Experimental Results

Numerical experiments based on the data given in Figure 1 and in Table 1 arecarried out under various conditions. Figure 3 shows the average time evolutionsof f1 and f2 over 40 runs each on a SUN Ultra30 workstation. The programs are
written in C language, and each run takes about 25 minutes of CPU time. All
experiments were conducted under these conditions: the population size P = 9,
the crossover and mutation rate pcross = 0.2 and pmut = 0.02 respectively,f1 , f2

f1 , f2

(a)

(b)

240

500

IIIf2

200
400

V f2

VIf2

160

If2

300

IIIf2

120

IIf2

200

IVf2

80
100

IIIf1

IVf1
V,VIf1

40

IIf1

0

0
0

500

If1

1000

1500

2000
STEPS

0

500

IIIf1

1000

1500

2000
STEPS

Fig. 3. Time evolutions of f1 and f2 under (a) fixed and parameterized fitness functions,and (b) different D settings

probabilities for each mutation: p1 = 0.2, p2 = 0.45, p3 = 0.1 and p4 = 0.25,
L1 = 250, L2 = 2000 and  = 0.99 are used. These values are determined basedon preliminary experiments. Results are summarized in Table 2. In Figure 3(a),the number of operators D is fixed to 105 as in [9]. In the figure, the results ofthree different fitness functions are compared: (I) the same fitness function usedin [9], (II) f α with α = 1, and (III) the parameterized f α with α decreasingfrom 1 to 0. It is clear that by using the parameterized fitness function, thequality of f2 greatly improves while the constraint f1 = 0 is satisfied at the endof the computation.
In Figure 3(b), the null mutation M5 is applied as well as M1,. . .,M4 to makeD changeable. D is initialized as D0 = 120 under (V) and D0 = 105 under (VI)respectively, and can be varied during the search with D0 the upper bound. p4 is
modified from 0.25 to 0.25 × (1 − 1/Ns ), and p5 = 0.25 × 1/Ns with Ns numberof shift types. The results of fixed D with (III) D = 105 and (IV) D = 100 are
also shown for comparison. It can be seen that changing D dynamically results
in better performance, with the optimal D around 102–103. The results under(IV) suggest that it is quite difficult to find a good solution with f1 = 0 whenD ≤ 100. The best results are obtained when the perameterized fitness function
and the modified mutation is used. Figure 4 shows one of the best schedules
obtained under (VI). The picture on the right in Figure 4 shows the schedule,
where the x axis represents time and the y axis the chosen working patterns.
The filled block indicates that an operator is at work, while each small whiteblock is a ten-minute break. Among 105 operators initially assigned, a total of
102 operators were found to be actually necessary, and the total surplus is 97,
meaning that only 0.54 operators on average are redundant per time interval. The
picture on the left shows the corresponding time distribution of the operators.

80

100
90
80

60
Operator Number

Number of Operators

70

50
40
30

70
60
50
40
30

20

20

10

10

0
1
(8:00~8:05)

Time ( 5 min. units )1
180(22:55~23:00) (8:00~8:05)

Time ( 5 min. units )180(22:55~23:00)

Fig. 4. Example of a solution with D = 102, f1 = 0 and f2 = 97

6

Conclusions

We have developed a genetic algorithm with local search for the information
operator scheduling problem. The experimental results show that the use of aparameterized fitness function and null mutation improves the solution quality
with a smaller number of total operators, while satisfying the given constraints.
Future research will be to investigate the better control of α rather than decreasing it monotonically.

References
1. E.L. Allgower and K. George. Numerical Continuation Methods: An Introduction.
Springer-Verlag, 1990.
2. C. Bierwirth, D. Mattfeld, and H. Kopfer. On permutation representations forscheduling problems. In 4th PPSN, pages 310–318, 1996.
3. F. Glover and C. MacMillan. The general employee scheduling problem: An integration of MS and AI. Computers and Operations Research, 13(5):563–573, 1986.
4. S. Kobayashi, I. Ono, and M. Yamamura. An efficient genetic algorithm for job
shop scheduling problems. In 6th ICGA, pages 506–511, 1995.
5. N.L.J. Ulder, E. Pesch, P.J.M. van Laarhoven, H.J. Bandelt, and E.H.L. Aarts.
Genetic local search algorithm for the traveling salesman problem. In 1st PPSN,
pages 109–116, 1994.
6. T. Yamada and R. Nakano. Job Shop Scheduling. Chapter 7 in A.M.S. Zalzala and
P.J.Fleming (Ed.) Genetic algorithms in engineering systems. The Institution ofElectrical Engineers, London, UK, 1996.
7. T. Yamada and R. Nakano. Scheduling by genetic local search with multi-stepcrossover. In 4th PPSN, pages 960–969, 1996.
8. T. Yamada and C.R. Reeves. Permutation flowshop scheduling by genetic local
search. In 2nd IEE/IEEE Int. Conf. on Genetic ALgorithms in Engineering Systems(GALESIA ’97), pages 232–238, 1997.
9. K. Yoshimura and R. Nakano. Genetic algorithm for information operator scheduling. In Proc. of 1998 IEEE Int. Conf. on Evolutionary Computation (ICEC’98),
pages 277–282, 1998.