2006-0540.tex

自动化学报的编辑软件

\end{align*}

\textbf{Theorem 1.} If there exists some $k^\ast $, such that $d\ge
\left| {{\rm {\bf {\pmb\lambda} }}_k -{\rm {\bf {\pmb\lambda}
}}^\ast } \right|^2$ and $\delta _k =0$ for $k\ge k^\ast $, then
Algorithm 1 converges, and the convergence efficiency is
\begin{align*}
&k-k^\ast
>
{d(L_f )^2} \mathord{\left/ {\vphantom {{d(L_f )^2} {(t_{\min }
(2-t_{\max } )\omega ^2(1-\omega )^2\varepsilon ^2)}}} \right.
\kern-\nulldelimiterspace} {(t_{\min } (2-t_{\max } )\omega
^2(1-\omega )^2\varepsilon ^2)} -\nonumber\\&{({(f({\rm {\pmb x}}_0
)-q({\rm {\bf {\pmb\lambda} }}_0 ))^2} \mathord{\left/ {\vphantom
{{(f({\rm {\bf x}}_0 )-q({\rm {\bf {\pmb\lambda} }}_0 ))^2}
\varepsilon }} \right. \kern-\nulldelimiterspace} \varepsilon )^2}
\mathord{\left/ {\vphantom {{({(f({\rm {\bf x}}_0 )-q({\rm {\bf
{\pmb\lambda} }}_0 ))^2} \mathord{\left/ {\vphantom {{(f({\rm {\bf
x}}_0 )-q({\rm {\bf {\pmb\lambda} }}_0 ))^2} \varepsilon }} \right.
\kern-\nulldelimiterspace} \varepsilon )^2} {(2e\ln (\omega ))}}}
\right. \kern-\nulldelimiterspace} {(2e\ln (\omega ))} \Rightarrow
q_k^{up} -q_k <\varepsilon.
\end{align*}


The proof of the lemmas and theorem is similar to those in [20, 21].
When some $k^\ast $ is obtained such that $\delta _k =0$ for $k\ge
k^\ast $, Algorithm 1 converges to the global optimal solution by
the efficiency given in Theorem 1. The efficiency of the whole
algorithm also depends on the efficiency to get $k^\ast $, which is
determined by the original $d$ and sequence $\delta _k $. If $\delta
_k $ is large before $d\ge \left| {{\rm {\bf {\pmb\lambda} }}_k
-{\rm {\bf {\pmb\lambda} }}^\ast } \right|^2$ is obtained and
descends to 0 sharply after $d\ge \left| {{\rm {\bf {\pmb\lambda}
}}_k -{\rm {\bf {\pmb\lambda} }}^\ast } \right|^2$ is obtained, then
$d$ will get larger rapidly to exceed $\left| {{\rm {\bf
{\pmb\lambda} }}_k -{\rm {\bf {\pmb\lambda} }}^\ast } \right|^2$. It
is better if the original $d$ is more close to $\left| {{\rm {\bf
{\pmb\lambda} }}_k -{\rm {\bf {\pmb\lambda} }}^\ast } \right|^2$.

Though Algorithm 1 converges without any prior knowledge, it is
correspondingly complicated to obtain $q_k^{lev} $. If the original
problem is feasible, it can be concluded that $q({\rm {\bf
{\pmb\lambda} }}^\ast )=J^\ast =0$, the algorithm could be reduced
by fixing $q_k^{lev} =0$.


\subsection{Sub-problems}
Each of the sub-problems involves only one event, so it is correspondingly
simple. We solve the sub-problems with enumeration method.

\subsection{Construct feasible solutions}
Since the field constraints are relaxed, the solutions obtained in the
iteration process would violate the field constraints, based on which we
must construct feasible solutions. In our work, a heuristic method is
developed. The method enumerates all the matches in the order of beginning
time, and postpones the current beginning time where the field constraints
are violated.

\section{Numerical results}
The algorithm has been implemented using Matlab and tested on
Celeron 4, CPU 1.4 GHz, 256 M SDRAM. The Olympics lasts for 16 days
around, but any group of events which are field-coupled one another
do not last longer than the track and field, which last for about 10
days. For the tested problem, we deal with the events during 7 days,
and each day is partitioned into 3 periods, each period is
partitioned into 9 time intervals. Each match lasts for 1--5
intervals, and all matches spread uniformly on the time axis. All
the numbers of intervals and beginning times are generated randomly.
The problem involves 20--90 events, and for a fixed number of
events, the problem is generated and computed 25 times.

In the numerical results by Algorithm 1, $J_{max}$ is the maximal
$J$ that arises in the optimization process, which denotes the
maximal cost of violating the final time constraints. And $\vert
q\vert _{max}$ is the absolute value of the minimal $q$, which is
the minimal dual value. The difference between $J$ and $q$ is the
gap of the original scheduling problem and the dual problem, which
is the measurement of the computational error.

If $J_{min}$/$J_{max}$ is smaller than a certain value, it can be
decided that an acceptable solution is obtained, which violates the
final time constraints not badly. If some $q>$0 is got, it can be
decided that the original scheduling problem is unsatisfiable, {\sl
i.e.} there are no solutions which satisfy all the constraints. And
as a practical criterion, we can set a positive value \underline
{\textit{q}} to judge that a scheduling problem is unsatisfiable if
$q>$\underline {\textit{q}}.

By the results, the ratio of the total time consumed and the number
of events is nearly a constant under the fixed steps of iteration.
$J_{min}$/$J_{max}$, $\vert q\vert _{min}$/$\vert q\vert _{max}$,
the time to get $ J_{min }$ and the number of tests to get $q>$0
increase as the number of events increases. All the possible
solutions of the problems can be obtained in no more than 10 mins.
The phase transition can be recognized by the number of tests to get
$q>$0 and the time first to get $q>$0.

The phase transition is shown in Fig.2, where the $x$-coordinate is
the number of events, the $y$-coordinate is the number of tests not
to get $q>$0 and the average time first to get $q>$0. From 40 to 70
on the $x$-coordinate, the number of tests not to get $q>$0
decreases fast, and the average time first to get $q>$0 is
distinctly longer than that outside the region.

Consider the numerical results by the reduced algorithm. The average
$J_{min}$/$J_{max}$ $'$s of the variable event number are shown in
Fig.\,3. And the average time to get $J_{min}$ by Algorithm 1 and
the reduced algorithm are shown in Fig.\,4. Fig.\,3 shows that when
the number of events is larger than 50, the average
$J_{min}$/$J_{max}$ increases fast. Comparing to the results by
Algorithm 1, phase transition happens around 50 events. So it can be
concluded that an original problem is infeasible if
$J_{min}$/$J_{max}$ is larger than a certain value. Fig.\,4 shows
that when the event number is smaller than 40, the difference
between the average times to get $J_{min}$ by Algorithm 1 and the
reduced algorithm are not notable, when the event number is larger
than 40, the time by Algorithm 1 is remarkably larger than that by
the reduced algorithm, and the difference has a maximal value
between 60 and 70. Figs 3 and 4 cannot provide enough information to
recognize the phase transition.

\vskip8mm {\centering

\vbox{\centerline{\psfig{figure=02.eps,width=6cm}} \vskip2mm {\small
Fig.\,2\quad Phase transition }}} \vskip5mm

{\centering

\vbox{\centerline{\psfig{figure=03.eps,width=6cm}} \vskip2mm {\small
Fig.\,3\quad Average $J_{min}$/$J_{max}$ }}} \vskip3mm

{\centering

\vbox{\centerline{\psfig{figure=04.eps,width=6cm}} \vskip2mm {\small
Fig.\,4\quad Average time to get $J_{min}$ }}}\vskip3mm

All the above numerical results show that Algorithm 1 and the
reduced algorithm can both be applied to the Olympics scheduling
problem. Algorithm 1 is more suitable for recognizing the phase
transition while the reduced algorithm is less time consuming.


\section{Conclusion}
In this paper, the Olympics scheduling problem is modeled as a
constraint satisfaction problem. By softening the time constraints
of the final matches, the constraint satisfaction problem is
transformed into a constrained optimization problem. A decomposition
methodology based on Lagrangian relaxation is presented for the
constrained optimization problem. The dual problem optimization is
the key challenge, for which the subgradient 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 Algorithm 1.



\begin{thebibliography}{99}
\zihao{6} \addtolength{\itemsep}{-0.6em} \urlstyle{rm}
\bibitem{1} Nemhauser G L, Trick M A. Scheduling a major college basketball
conference. {\sl Operations Research}, 1998, {\bf 46}(1): 1--8

\bibitem{2} Henz M. Scheduling a major college basketball conference - revisited.
{\sl Operations Research}, 2001, {\bf 49}(1): 163--168

\bibitem{3} Schaerf A. Scheduling sport tournaments using constraint logic
programming. {\sl Constraints}, 1999, {\bf 4}(1): 43--65

\bibitem{4} Regin J C. Modeling and solving sports league scheduling with
constraint programming. In: Proceedings of the First Congress of the
French Operational Research Society (ROADEF). Paris, France, 1998

\bibitem{5} McAloon K, Tretkoff C, Wetzel G. Sports league scheduling. In:
Proceedings of the 3rd ILOG Optimization Suite International
Users$'$ Conference. Paris, France, 1997

\bibitem{6} Sch\"{o}nberger J, Mattfeld D C, Kopfer H. Memetic algorithm
timetabling for non-commercial sport leagues. {\sl European Journal
of Operational Research}, 2004, {\bf 153}(1): 102--116

\bibitem{7} Andreu R, Corominas A. Succces 92: A DSS for scheduling the
Olympics. {\sl Interfaces}, 1989, {\bf 19}(5): 1--12

\bibitem{8} Burke E K, Petrovic S. Recent research directions in automated
timetabling. {\sl European Journal of Operational Research}, 2002,
{\bf 140}(2): 266--280

\bibitem{9} Luh P B, Hoitomt D J, Max E, Pattipati K R. Schedule generation
and reconfiguration for parallel machines. {\sl IEEE Transactions on
Robotics and Automation}, 1990, {\bf 6}(6): 687--696

\bibitem{10} Luh P B, Debra J H. Scheduling of manufacturing systems
using the Lagrangian relaxation technique. {\sl IEEE Transactions on
Automatic Control}, 1993, {\bf 38}(7): 1066--1079

\bibitem{11} Hoitomt D J, Luh P B, Pattipati K R. A practical approach
to job-shop scheduling problems. {\sl IEEE Transactions on Robotics
and Automation}, 1993, {\bf 9}(1): 1--13

\bibitem{12} Chen H X, Chu C B, Proth J M. An improvement of the
Lagrangean relaxation approach for job shop scheduling: a dynamic
programming method. {\sl IEEE Transactions on Robotics and
Automation}, 1998, {\bf 14}(5): 786--795

\bibitem{13} Luh P B, Gou L, Zhang Y H. Job shop scheduling with
group-dependent setups, finite buffers, and long time horizon. {\sl
Annals of Operations Research}, 1998, {\bf 76}: 233--259

\bibitem{14} Zhang Y H, Luh P B, Narimatsu K, Moriya T, Shimada T, Fang
F. A macro-level scheduling method using Lagrangian relaxation. {\sl
IEEE Transactions on Robotics and Automation}, 2001, {\bf 17}(1):
70--79

\bibitem{15} Polyak B T. Minimization of unsmooth functionals. {\sl USSR
Computational Mathematics and Mathematical Physics}, 1969, {\bf 9}:
14--29

\bibitem{16} Kiwiel K C. The efficiency of subgradient projection methods
for convex optimization, Part I: general level methods. {\sl SIAM
Journal of Control and Optimization}, 1996, {\bf 34}(2): 660--676

\bibitem{17} Kiwiel K C. The efficiency of subgradient projection methods
for convex optimization, Part II: implementation and optimization.
{\sl SIAM Journal of Control and Optimization}, 1996, {\bf 34}(2):
677--697

\bibitem{18} Kim S, Ahn H, Cho S. Variable target value subgradient
method. {\sl Mathematical Programming}, 1991, {\bf 49}: 359--369

\bibitem{19} Cheeseman P, Kanefsky B, Taylor W M. Where the really hard
problems are. In: Proceedings of the 12th International Joint
Conference on Artificial Intelligence. 1991

\bibitem{20} Jiang Yong-Heng. Bottleneck Analysis and Coordination of
Supply Chain. [Ph.D. dissertation], Tsinghua University, 2003 (in
Chinese)

\bibitem{21} Jiang Yong-Heng, Zhou Wei, Jin Yi-Hui. Subgradient
projection method with variable diameter for optimization. {\sl
Control and Decision}, 2004, {\bf 19}(3): 303--306 (in Chinese)
\end{thebibliography}

\begin{biography}[jiangyongheng.eps]
\noindent{\bf JIANG Yong-Heng }\quad Received his Ph.\,D. degree
from Tsinghua University in 2003. He is currently a lecturer in
Tsinghua University, and his research interest covers analization
and optimization of complex system, and scheduling and planning.
Corresponding author of this paper. E-mail: [e-mail]
\end{biography}

\vskip8mm

\begin{biography}[guqinghua.eps]
\noindent{\bf GU Qing-Hua }\quad Received his master degree from
Tsinghua University in 2006. His research interest covers system
designing and optimization.
\\
E-mail: [e-mail]
\end{biography}

\vskip14mm

\begin{biography}[huangbiqing.eps]
\noindent{\bf HUANG Bi-Qing }\quad Received his Ph.\,D. degree from
Tsinghua University in 1994. He is currently an associate professor
in Tsinghua University, and his research interest covers game
management, service theory, and material grid.\\ E-mail:
[e-mail]
\end{biography}

%\end{multicols}
\end{document}