于海军366-北京大学教务部.docVIP

大型科技会议议程安排问题 The Scheduling of Large Academic Conference 北京大学数学学院98级 于海军 摘要 本文利用图论作为工具讨论了一般科技会议的议程安排问题，给出了议程确定的一些准则，并对不同的情况给出了用计算机进行自动安排议程的算法。本文主要的实例是1998年在德国举行和2002年将在北京举行的两届世界数学家大会。作者利用本文的算法实现了一个议程安排程序，可以方便地解决各种大型会议的议程自动安排问题。 Abstract With graph theory, this article analysis the scheduling of normal academic conferences, and give an algorithm of schedule planning. The main examples of this article are the two International Conference of Mathematics just held in Berlin 1998 and will hold in Beijing 2002. A computer program was made according to the algorithm. It can give the scheduling of kinds of large-scale academic conferences. 一、议程安排问题的数学描述 （一） 问题的提出 在各种国际学术交流中，召开学术会议是最直接的了。目前的国际学术会议种类有很多，规模也在逐渐变大。往往出席人数超过千人，会议场次超过百场，可能分多个专题小组，这就涉及到议程安排问题。以1998年在德国柏林举行的世界数学家大会为例：参加人数超过4000人，分为19个小组，在10天的时间内（包括一个休息日）共安排了大会报告21场，邀请报告164个，口头报告和书面报告1171个。如何将这些报告安排在9天的时间内，使它们互不冲突，这就是议程安排问题。 需要指出的是，科技会议议程安排问题之所以能成为一个数学问题是因为这种会议除了大会形式之外还有分组会议，存在大量的并行进行的场次。因此，如果两个场次中有同样的主持人或者发言人，那么这两个场次就不能同时进行；一般情况下，属于同一个分组的场次也不能同时进行。如果会议没有分组，也就没有同时进行的场次，那么议程安排就是一个简单的排序。 （二） 问题的数学描述 原始问题 议程安排考虑的主要对象是：场次、时间片和会场。场次由会议的程序委员会确定，时间片由组委会根据惯例或者当地的作息情况确定，会场是组委会根据对会议的人数、场次等项的估算而安排给会议使用的会场。场次有以下几个属性：“分组”、“会场大小要求”、“房间媒体要求”、“主持人”、“所有发言人”、“场次类型”；会场有“人数”、“媒体配置”两个属性；时间片有“类型”一个属性，不同类型的时间片有不同的时间长度，对应于不同的场次类型，一般为了安排的方便，各个时间片之间是不重叠的。如果会议场次多且关系复杂，可以给不同类型的场次集合分配不同类型且不相交的时间片集合，从而将一个庞大的议程安排问题分解成几个较小的议程安排问题，使问题的规模降低。 定义两个场次固有冲突，如果两个场次属于相同的分组或者两个场次有相同的主持人或发言人。 如果两个场次有固有冲突，则它们不能安排在同一个时间片内。一般来说，除了固有冲突，议程安排者可能会不希望特定的两个场次同时进行甚至会希望一个场次一定要在另一个场次之前进行。我们把所有这些场次与场次之间的关系叫做冲突关系或限制关系。把前者叫做无序冲突或无序限制，后者叫做有序冲突或有序冲突。 议程安排问题就是在场次、会场、时间给定的情况下， 为每个场次指定一个时间片，一个会场，并且使得有 有冲突的场次不在相同的时间片内，对于有序冲突，场次要满足序的限制。 同一时间同一会场最多一个场次 会场的大小、媒体配置要符合场次的要求。 条件的简化 将场次的房间大小，媒体要求与每一个会场做比较，可以得到每个场次的可用房间列表，可以用一个0、1矩阵A表示,A(i,j)=1表示第i个场次可以使用第j个房间，否则表示不可以使用。 场次之间的冲突关系可以用一个有向图表示。场次作为端点，冲突关系作为边。如果是规定了顺序的冲突，就是有向边，否则是无向边。这个图在议程安排之前计算出来，它可以用两个0、1矩阵表示，一个表示有序冲突，其对应矩阵A满足：若A(i,j)=1,A(j,k)=1 则A(i,k)=1;另一个表示无序冲突相应的矩阵是对称的。 数学表述 给定场次集合为 ，会场集合为 ，时间片数为k,无序冲突矩阵,有序冲突矩阵,场次会场可用关系矩阵 ,议程安排问题