2006-0540.tex

自动化学报的编辑软件

\documentclass{aase}
\usepackage{multicol}
\usepackage{psfig}
\usepackage{subfigure}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{url}
\usepackage{ccaption}
\usepackage{booktabs} % 做三线表的上下两条粗线用

\setcounter{page}{409}

\firstheadname{ACTA AUTOMATICA SINICA} % 首页页眉
\firstfootname{} % 首页页脚 \zihao{5-}$\copyright$ 200X by {\sl Acta Automatica Sinica}. All rights reserved.
\headevenname{ACTA AUTOMATICA SINICA} % 其他页偶数页页眉
\headoddname{JIANG Yong-Heng et al.: Model Transformation and Optimization of the Olympics $\ldots$}% 其他页奇数页页眉
\begin{document}

\title{{
Model Transformation and Optimization of\\\vskip 0.4\baselineskip
the Olympics Scheduling Problem }
\thanks{
Received
June 16, 2006;
in revised form
October 2, 2006
}
\thanks{
Supported by Beijing Natural Science Foundation of P.\,R.\,China
(4031002) }
\thanks{
1. Department of Automation, Tsinghua University, Beijing 100080,
P.\,R.\,China }
\thanks{DOI: 10.1360/aas-007-0409}}

\author{{
JIANG Yong-Heng$^{1}$ \qquad GU Qing-Hua$^{1}$ \qquad HUANG
Bi-Qing$^{1}$ \qquad CHEN Xi$^{1}$ \qquad XIAO Tian-Yuan$^{1}$ } }

\abstract{ The Olympics scheduling problem is modeled as constraint
satisfaction problem, which is transformed into a constrained
optimization problem by softening the time constraints of the final
matches. A decomposition methodology based on Lagrangian relaxation
is presented for the constrained optimization problem. For the dual
problem optimization the sub-gradient projection method with
variable diameter is studied. The method can converge to the
globally optimal solutions and the efficiency is given. Numerical
results show that the methods are efficient and the phase transition
domain can be recognized by the algorithm. }

\keyword{ Scheduling, Olympics, Lagrangian relaxation, model
transformation}
%\cncl{TPXXX.XX}

\maketitle

\pagestyle{aasheadings}

%这一章为引言,无需写标题. We do not need a title for the introduction chapter.

{\renewcommand\baselinestretch{2.0} Since 1980s, modern sports
activities have been more and more socialized, specialized,
entertainized, commercialized and informatized. As time flies, new
technologies play more and more important roles in sports
organization. And ``High-tech Olympics'' has been one of the three
themes of ``New Beijing, Great Olympics''. Research progress on
``High-tech Olympics'' will benefit the society and economy
development.

Olympics organization involves quite many sorts of resources,
athletes, referees and gymnasia, as long with various constraints.
So the Olympics scheduling is an arduous task, which is one of the
important branches of the ``High-tech Olympics'' research. Sports
scheduling research originated in the 1980s. Nemhauser and
Trick$^{[1]}$, Henz et al.$^{[2]}$, Schaerf$^{[3]}$, Regin$^{[4]}$,
McAloon, Tretkoff and Wetzel$^{[5]}$, Sch\"{o}nberger, Mattfeld and
Kopfer$^{[6]}$ have explored the scheduling problem. But they
focused on the single-event tournament scheduling problem. Research
on multi-event and large scaled scheduling research has not been
reported. Andreu$^{[7]}$ has studied the DSS for scheduling the 1992
Olympic Games, but the algorithm was not studied.

The Olympics scheduling problem is a timetabling problem. The
timetabling problem is a combination problem in nature, and has been
proven NP-hard. A wide variety of approaches to timetabling problems
have been described in the literature and tested on real data. They
can be roughly divided into four types$^{[8]}$: 1) sequential
methods, 2) cluster methods, 3) constraint-based methods, and 4)
meta-heuristic methods. Sequential methods and cluster methods
present policies that obtain approximate solutions. Constraint-based
methods are back-tracking methods in nature. Meta-heuristic methods
can provide good solutions, but they are computational consuming.

A novel method might be found by transforming the problem into a new
model. In this paper, the time constraints of the final matches are
softened, and then the Olympics scheduling problem is transformed
into a constrained optimization problem. Although the events are
coupled by the field constraints, the constrained optimization
problem can be decomposed into single-event sub-problems by relaxing
the field constraints. Lagrangian relaxation provides a methodology
to realize the decomposition. Since 1990s, the authors such as Luh,
et al. have studied the production scheduling problem with
Lagrangian relaxation$^{[9-14]}$. They relaxed the capacity
constraints to decompose the production scheduling problem into job
sub-problems. The difficulty of Lagrangian relaxation is the
optimization of the dual problem. In 1969, Polyak$^{[15]}$ presented
a subgradient method to the convex problem, but the convergence of
the method depended on the estimated optimal value. In 1996,
Kiwiel$^{[16-17]}$ studied the subgradient projection methods for
convex optimization, which converged without the estimated optimal
value, but the diameter of the variable domain was imported.
Kim$^{[18]}$ had presented a variable target value subgradient
method in 1991 before Kiwiel, which was nothing but a special case
of Kiwiel$'$s method.}

\section{Temporal interval model language}

{\renewcommand\baselinestretch{2.0} The Olympics system involves
time-distribution constraints, field constraints, person constraints
and time window constraints. A temporal interval model language is
needed as the interface to deal with the constraints.

The matches are scheduled in the periods of the competition days,
and the periods are not continuous. So a triple $(d,p,\tau )$ is
designed for time $t$, $d=1,\cdots ,n$ denotes the days,
$p=0,1,\cdots ,p_m -1$ denotes the periods ($p_m $ is the number of
the periods in a day), and $\tau =[0,1,\cdots ,\tau _m -1]$ denotes
the time point ($\tau _m $ is the number of the time points in a
period). In the Olympics scheduling problem, the $k$th match of
event $i$$'$s $j$th round is denoted as $(i,j,k)$, and the final
match is denoted as $(i,j_{mi} ,1)$. The beginning time and ending
time of $(i,j,k)$ is denoted as $T_{bijk} $ and $T_{eijk} $, the
corresponding triples are $(d_{bijk} ,p_{bijk} ,\tau _{bijk} )$ and
$(d_{eijk} ,p_{eijk} ,\tau _{eijk} )$. The relations for time
intervals are as follows.\\

1) equal $[t_{11} ,t_{12} ]=[t_{21} ,t_{22} ]\Leftrightarrow t_{11}
=t_{21} \wedge t_{12} =t_{22} $.\vskip1mm

2) before $[t_{11} ,t_{12} ]<[t_{21} ,t_{22} ]\Leftrightarrow t_{12}
<t_{21} $.\vskip1mm

3) after $[t_{11} ,t_{12} ]>[t_{21} ,t_{22} ]\Leftrightarrow t_{11}
>t_{22} $.\vskip1mm

4) repulsive $[t_{11} ,t_{12} ]\mathop \leftrightarrow \limits_{c_2
}^{c_1 } [t_{21} ,t_{22} ]\Leftrightarrow t_{12} +c_1 <t_{21} \vee
t_{11} >t_{22} +c_2 $.\vskip1mm

5) close $[t_{11} ,t_{12} ]\mathop \approx \limits_{c_2 }^{c_1 }
[t_{21} ,t_{22} ]\Leftrightarrow t_{11} \le t_{22} +c_2 \wedge
t_{12} +c_1 \ge t_{21} $.\vskip1mm

6) including $[t_{11} ,t_{12} ]\supset [t_{21} ,t_{22}
]\Leftrightarrow t_{11} \le t_{21} \wedge t_{12} \ge t_{22}
$.\vskip1mm

7) during $[t_{11} ,t_{12} ]\subset [t_{21} ,t_{22} ]\Leftrightarrow
t_{11} \ge t_{21} \wedge t_{12} \le t_{22} $.\\

The rules above are used to model the Olympics scheduling problem of
a schedule system.}

\section{Modeling and model transforming of the Olympics scheduling problem}
In Olympics, the athletes hope to play fairly, the audience want
their favorable matches, the sponsors require the gainful
advertisement time, and the matches run in some special orders.

For most events, teams or athletes take part in some matches, and
the winners are promoted to the next round until the champion is
chosen. There are one or more matches in a round, and the matches of
the preceding round have to be earlier than those of the successor.
These are called order constraints. Some special event has just one
round. For some traditional or other reasons, a special round of
event A must run before the related round and after the preceding
round of event B, for example, swimming man and swimming woman.
These are called cross constraints. Some event cannot be much
earlier or later than some other event. These are called close
constraints. Some event has to be some time earlier or later than
some other event. For example, the different groups of the same
event had better run one after another, the track events longer than
1000 meters cannot run in a same day. These are called
decentralization constraints. All of the above constraints are
called time-distribution constraints.

The capacity of the fields is limited, so there cannot be much more matches
on the fields at the same time. Some fields may affect each other, and there
cannot be matches on the correlative fields at the same time. And these are
called field constraints.

In Olympics, some athlete may attend more than one event. So there has to be
some time interval between the correlative events, and the athlete cannot
run from one field to another in a period of time. These are called person
constraints.

The audience and sponsors$'$ requirement could be expressed by time
window constraints.

In fact, the events of the Olympics are coupled by the field
constraints. The field uncoupled events could be schedule
respectively and independently. Next, a kind of field coupled events
represented with the temporal interval model language are analyzed
and formulated in Section 2.

First, some symbols are explained. If event $i$ can run on the kind
of field $l$, $S(i,l)=1$, otherwise, $S(i,l)=0$. If match $(i,j,k)$
runs on the $m$th field at time $t$, $O[(i,j,k),m,t]=1$, otherwise,
$O[(i,j,k),m,t]=0$.

The constraints are formulated as follows:

1) Time-distribution constraints

Order constraints are as follows

\begin{equation}[T_{bi_1 j_1 k_1 } ,T_{ei_1 j_1 k_1 } ]<[T_{bi_2 j_2 k_2 } ,T_{ei_2 j_2 k_2 } ]
\end{equation}

Cross constraints are as follows

\begin{align}
&[T_{bi_1 jk_1 } ,T_{ei_1 jk_1 } ]<[T_{bi_2 jk_2 } ,T_{ei_2 jk_2 }
]\wedge [T_{bi_2 jk_2 } ,T_{ei_2 jk_2 } ]<\nonumber\\&[T_{bi_1
j+1k_1 } ,T_{ei_1 j+1k_1 } ]
\end{align}

Decentralization constraints are as follows

\begin{equation}
[T_{bi_1 j_1 k_1 } ,T_{ei_1 j_1 k_1 } ]\mathop \leftrightarrow
\limits_{c_2 }^{c_1 } [T_{bi_2 j_2 k_2 } ,T_{ei_2 j_2 k_2 } ]
\end{equation}

Close constraints are as follows

\begin{equation}
[T_{bi_1 j_1 k_1 } ,T_{ei_1 j_1 k_1 } ]\mathop \approx \limits_{c_2
}^{c_1 } [T_{bi_2 j_2 k_2 } ,T_{ei_2 j_2 k_2 } ]
\end{equation}

2) Field constraints

\begin{equation}
\forall l,t,\ \sum\limits_{i:S(i,l)=1} {O[(i,j,k),m,t]\le m_{\max }
}
\end{equation}

There cannot be more than $m_{\max } $ matches on the $m$th field at
the same time.

3) Person constraints

\begin{equation}
[T_{bi_1 j_1 k_1 } ,T_{ei_1 j_1 k_1 } ]\mathop \leftrightarrow
\limits_{c_2 }^{c_1 } [T_{bi_2 j_2 k_2 } ,T_{ei_2 j_2 k_2 } ]
\end{equation}

Matches $(i_1 ,j_1 ,k_1 )$ and $(i_2 ,j_2 ,k_2 )$ involve some
common athletes, so match $(i_1 ,j_1 ,k_1 )$ must be repulsive to
match $(i_2 ,j_2 ,k_2 )$.

\begin{align}
&O[(i,j,k_1 ),m_1 ,t_1 ]=1\wedge O[(i,j,k_2 ),m_2 ,t_2
]\nonumber\\&=1\wedge \left| {t_1 -t_2 } \right|\le\tau \Rightarrow
m_1 =m_2
\end{align}

Matches $(i_1 ,j_1 ,k_1 )$ and $(i_2 ,j_2 ,k_2 )$ involve some
common athletes. If they are time-close, they must occupy the same
field.

4) Time window constraints