Finding a feasible course schedule using Tabu search(3)


  • [#] 介绍
  • [#] 问题描述
  • [#] 禁忌搜索技术
  • [#] 修改禁忌搜索
  • [ ] 数字化结果
  • [ ] 扩展
  • [ ] 结束语


Many authors have formulated the course scheduling problem as an assignment
problem [3,4,9,12]. Guidelines for adapting Tabu search to assignment problems
have been described in [12]; the same paper contains a description of the algorithm
TAT1 which is an example of such an adaptation to a course scheduling problem
where starting times have to be assigned to courses. For our timetabling problem
we cannot use the algorithm TAT1 since the number of courses and their length are
not known in advance.
Let us however formulate our course scheduling problem as an assignment problem
where each element from a set S of conflicting objects is assigned to exactly one
element of a set P.
The daily quantums of a static topic are fixed in advance. They induce courses
of given length. These courses are defined to be s-objects.

We shall consider each time period of a dynamic topic as a second kind of objects
which are called d-objects.
The set S consists of all s-objects and d-objects, and the set P consists of all
available time periods. Now, an available time period of a working day has to be
assigned to each object of S; for an s-object the time period represents the starting
time of the course. Any assignment satisfying all the constraints (a)-(i) induces a
feasible course schedule.

The set X of feasible solutions

Eiselt and Laporte [7] have divided the requirements into hard, medium and soft
ones. The hard requirements have to be respected at all costs while soft ones are only
desirable; medium requirements should be satisfied but are nevertheless relaxable.
In most approaches, a timetable is defined to be feasible if it satisfies all hard requirements:
soft requirements are modelled as objectives while hard ones appear as
constraints. The solution methods designed for dealing with timetabling problems
usually consist of two phases: in phase I a heuristic procedure tries to find a feasible
timetable, and in phase II the current solution is improved by satisfying more
medium or soft requirements and without violating any hard one.
Let us define the following state-space graph G:

  • each feasible timetable is a node in G,
  • an arc links node x to node y if y is considered as an improvement of x in phase
    Phase I can be viewed as a generation of a node in G, and phase II is a descent
    method which moves step by step in the state-space graph G until a local optimum
    is reached. For large scale timetabling problems, finding a feasible course schedule
    is not an easy task. Moreover, if phase I succeeds in finding a feasible solution, this
    solution and the best one are not necessarily in the same connected component of G.
    We shall define a connected state-space graph G: and phase II will be replaced
    by an adaptation of Tabu search techniques. We have now to define the set X of
    feasible solutions, that is the nodes of the state-space graph G.
    There are two ways for handling with a constraint: it can either be satisfied by
    each solution of the set X of feasible solutions, or else it can be penalized in the objective
    function. It is to be decided which from among all the requirements will
    always be satisfied and which one will be penalized.
    An object should never be assigned to a time period if such an assignment can
    only induce course schedules which are not feasible. For example, each object is a
    portion of a subject x and thus should never be scheduled after the due date or
    before the release date of x. For this reason, constraint (e) should always be
    On the other hand, a conflict between two objects should not be a sufficient condition
    for hindering an assignment.
    Constraint (a) for example should only be penalized and not always satisfied.
    Guided by these ideas, it was decided to penalize constraints (a)-(d) and always
    satisfy constraints (e)-(h).
    Constraint (i) has been split into two distinct requirements: (i1) (respectively (i2))
    requires that the minimal (respectively maximal) number of consecutive time periods
    of each daily quantum of a dynamic topic is not violated.
    It was decided to penalize (i1). This choice is justified by the fact that the assignment
    of exactly one object is changed at each iteration of the Tabu search procedure:
    for dynamic topics this means that one time period is moved at a time, and
    removing from a working day a whole daily quantum with minimum value > 1 can
    only be achieved by violating constraint (il). Constraint (i2) is included in the set
    of always satisfied requirements since any feasible schedule can always be obtained
    without violating this requirement.
    For a dynamic topic, the set of d-objects which are scheduled on the same day
    is defined to be a course. Let us consider a course of a dynamic topic satisfying constraint
    (g). The following modifications can be obtained with several steps of the
    Tabu search procedure while always satisfying constraint (g):
  • the amount of consecutive time periods is not changed but the course is moved
    to another portion of the working day,
  • the daily quantum is increased or decreased.
    These justify our decision to never violate requirement (g).
    Constraint (h) has to be considered more carefully. If a static topic can only be
    scheduled in a number n of different working days and if its number of daily quantums
    is equal to n then constraint (h) should only be penalized since the daily quantums
    are not necessarily correctly ordered, and satisfying constraint (d) can then
    only be achieved by violating requirement (h). But this case is not frequent in real life
    timetabling problems and it was supposed that such a situation does not occur.
    Moreover, the definition of a course of a dynamic topic implies that constraint (h)
    is satisfied for any dynamic topic. For these reasons, it was decided to forbid any
    solution violating requirement (h).
    In summary, the set X of feasible solutions contains any assignment of time
    periods to the objects of S such that constraints (e), (f), (g), (h) and (i2) are satisfied.

The objective function

For each topic t, we denote:
n(t): its number of daily quantums,
qi(t): (i= l,…, n(t)) one of its courses,
r(t): the minimum number of time periods in a daily qantum,
b(t): the first time period of course qi(t)
ei(t): the last time period of course qi(t)
B(t): the first time period of t (B(t) = min{ b,(t) |i = 1, . . . , n(t)}),
E(t): the last time period of t (E(t)=max(t) |i = 1, …,n(t))),
P(t): the set of immediate predecessors of t (if t1and t2 precede t and t1
precede t2, then only t2 belongs to P(t)).
If t is a static topic, then n(t) is fixed and qi(t) must precede qj(t) for any j>i.For a dynamic topic i, n(t) and the values ei(t) - bi(t) are variable.For two objects i and j of S, the value d(i, j) denotes the number of time periods during which i and j are held simultaneously. Since the length of an s-object may be greater than one, it follows that two objects assigned to different time periods can be in conflict. The class involved in an object i of S is denoted c(i), and t(i), is the teacher which gives the course. Let ntopic denote the number of topics.
For any solution s of X, the fallowing objective function f is defined:

The parameters p1, . . . ,p5 give relative weights to constraints (a), (b), (c), (d) and
(i1) respectiveiy. A solution s induces a feasible course schedule if and only if
f(s)=O= f *.

The neighborhood N(s)

A solution S’ ∈ X is considered as a neighbor solution of s in X if it is obtained
by changing the assignment of exactly one object o of a topic t. Let d be the current
working day in which o is assigned. In order to satisfy constraints (g) and (h), the
set of possible modifications must be restricted to ten types which are represented
in Fig. 2:

  • If o is an s-object, then it can be assigned to a new working day d’≠d which
    does not contain any course of I (type 1), or it can be moved to another portion of
    d (type 2).
  • If t is a dynamic topic and o is the first or the last time period of a course, then
    it can be assigned to any working day d’. If d’≠ d and d’ already contains a course
    q of t, then o can be placed exactly before the first time period of q (types 3, 4)
    or exactly after its last time period (types 5,6). If d’ ≠ d and d’ does not contain any
    course of I, then o can be assigned to any time period of d’ (types 7, 8). If d’= d,
    then the first time period of a course can be moved exactly after the last one (type
    9) and the last time period can be moved before the first one (type 10).
    Of course, all these modifications m are acceptable at s only if s⊕m = S’ belongs
    to x.

    The other ingredients

    When an object o currently scheduled on the working day d is moved to a new
    time period, the pair (0, d) is introduced in the tabu list T. This means that for |T|
    steps of the Tabu search procedure, it is not allowed to assign any time period of
    d to 0.
    The set V is generated randomly but contains only new assignments obtained by
    changing the starting time of an object which gives a strictly positive contribution
    to f(s). In other words, objects which respect all the constraints are not moved.
    In order to allow the tabu status of a move to be cancelled, we consider the
    penalization function a(s, m) = f (s⊕m) and the aspiration function A(s,m)= f (s
    许多作者都将排课问题形式化为分配问题[3,4,9,12]。为适应禁忌搜索到分配问题的指导方针在[12]已经描述; 包含算法的描述TAT1的相同的论文,这是开始时间必须被分配课程的一个课程调度问题的例子。对于我们的时间表问题我们不能使用算法TAT1,因为课程的数量和它们的长度是事先不知道的。


Eiselt和Laporte [7] 将需求划分为硬性、中性、软性。硬要求必须找到所有的解,而软要求是可取的,中性要求应该得到满足,但仍然比较宽松。

  • 每一个可行的时间表是在G中的一个节点,
  • 第二阶段如果y被认为是x的改进,画出节点x到节点Y的圆弧

另一方面,两个对象之间的冲突应是一个充分条件 用于阻止分配。例如约束(a)应该阻碍,而且不总是满足。
这由约束i1决定的。这种选择是由分配合理的恰好一个目的是在禁忌搜索过程的每一次迭代而改变:为动态的主题,这意味着一个时间段只能有一个移动,并通过约束i1从每天量与最小值> 1的工作日中去除。约束(I2)被包括在总是满足需求的集合中,因为总是可以在不违反这一要求的情况下得到任何可行的调度。


  • 连续时间周期的量没有改变,但课程被移动到其他工作日,
  • 每日量增加或减少。
    Qi(T):(i =1,…,N(t))课程之一,
    E(T):T的最后时间段(E(T)= max(t)|i = 1,…,N(T)))
    P(t):集合T的直接前辈(如果t1和 T2优于T、T1优于t2时,则T2只属于P(t))。


参数p1…..P5给出了约束(a), (b), (c), (d), (i1)相对权重。当且仅当f(s)=O= f *,解S可以归纳出可行的课程表。


  • 如果o为s-对象,那么他可以被安排到一个新的工作日d’≠d,且不包含任何类型1课程。
  • 如果t是一个动态的主题且o为所述第一或课程的最后一段时间,然后它可以被分配给任何一个工作日D’。如果D’≠D和D’已经包含t中的课程Q,那么O可以被确定的放到第一个时间之前(类型3,4)或确定的放到时间段之后(5,6型)。如果D’≠ D并且D’不包含任何课程I,可那么o可以被分配至d的任意时间段(类型7,8)。如果D’= D,那么课程的第一个时间段可以被移动到最后一个时间段之后(类型9),并且最后一个时间段可以移动到第一个时间段之前(类型10)。当然,当且仅当s⊕m = S’,那么这些修改m都是可接受的。



集合V 是随机产生的,但仅包含只改变起始时间的为f(s)做出正贡献对象的分配。换句话说,满足所有约束的对象是不移动的。
为了禁忌状态取消,我们定义惩罚函数a(s, m) = f (s⊕m)和启发函数A(s,m)= f (s