PMC-APS优化算法的魅力案例分析

1、APS优化算法的魅力：案例分析APSS高级计划与排程协会APS （Lean System Advanced Planning and Scheduling ）精益系统高级计划排程，是基于现实的资源能力、时间、产品、约束条件、逻辑关系等 有限资源能力情况，得到一个可实施的最佳计划排程方案。其核心在于一个优化算法的排程引擎LSAPS的应用范围极其广泛，除了制造业，交通、 物流、码头、电力、教育、医疗、体育、军事等等方面都可以应用。远程教育考试是怎么考的考试排程套用工业术语就是，几万个学生就是几万个订单；如果某个学生本次要考试五门功课，这个订单工序就是五道；一层BOM；资源 是分布在各地的几百个教室

2、和考卷；可变资源是必要时可以增加副卷A、B、C等。排程工作就是要在各种约束条件下，在最短时间（例如两三 天）把订单全部完成，并且可变资源用的最少。LSAPS （Lean System Advanced Planning and Scheduling）精益系统高级计划排程，是基于现实的资源能力、时间、产品、约束条件、逻辑 关系等有限资源能力情况，得到一个可实施的最佳计划排程方案。其核心在于一个优化算法的排程引擎。LSAPS的应用范围极其广泛， 除了制造业，交通、物流、码头、电力、教育、医疗、体育、军事等等方面都可以应用。在远程教育考试排程的应用就是一个典型案例。远程教育考试是中国特色的一种模式。

3、在说这个事情之前，需要说一下，和我们过去在学校的考试不同，最大的区别在于在一个考场的考生手 里拿到的考卷可能是不同科目的。否则大家可能不好理解是怎么考试的。我国的远程教育发展很快，目前经教育部批准，六十多所高等院校正在从事远程学历教育，在校生达到近百万。但是，每年的几次考试，排考 场和编考卷都是学校的一项极为繁重的工作。成千上万的学生，要在同一段时间，在全国一千多个不同的地点，完成多达一百到两门 不同专业的考试；与此同时，我们希望要求占用最少的时间。这个看似简单的问题其实包含了复杂的数学优化问题。因此，多年以来 各个学校都是依靠经验由教师手工排考场，当遇到冲突的时候不得已就增加考卷类型（增加A

4、卷、B卷、C卷），大大增加了教 师的工作量，浪费了很多宝贵的资源、资金和时间。远程教育考试排程最困难的是因为受到一些约束，例如，同一考生不能在同一时间参加一门以上的考试（硬约束）；同一份考卷不能在不同的 时间使用（防止泄密问题）；考生能不能连续几场考试（疲劳问题）等等。远程教育考试排程一直困扰着众多的高等院校的老师们。当学生数量和考试科目数量达到一定程度后，就是一个极其复杂和庞大的数学排列组 合问题。手工排程是一项非常繁重的劳动，最重要的是，排出的结果让考试拖的时间很长，或者同一门课程需要编出很多种不同的考 卷。事实上，各个学校的老师们也在使用软件来排程，也就是通常说的“规则算法”。虽然比手工

5、快多了，但是结果比手工排还差， 还需要人工调整；有人也建立了适当的数学模型，用通常的传统的优化算法，其求解过程将需要极为漫长的时间-SAPS的案例证明， 在比较短的时间（例如30分钟），对于数万名考生、几百门考试科目的一次考试任务，可以得到接近最优的排程方案。排程原则根据学生报名课程考试数据，系统按照优化算法合并课程，自动把所有课程的考试安排在设定的场次考试中，保证每个学生的课程考试不发生科目考生人数手工排程场次LSAPS场次:节纳场次卷数LSAPS试卷数节约试卷1429847210820%28116940%206851152520812冲突。系统在可用增加试卷类型的办法解决7考生人数手工排程

6、带A,B,C卷标识），并得出场次相对人数均衡、场次总数最少、总考卷数最少、考卷种类适中的最佳安排方案。考场排程与费用分析实测数据对比（上图！） 上面表格的数据实际是规模比较少的考生人数。LSAPS实际上对于越大的数据越复杂的系统越能发挥更大的作用。下面是一家比较大的网络教育机构的实际运用结果。该机构负责全国的三十多所高效的网络教育远程考试，拥有1000多个考试点。按照最保守的数据：优化排 程后，考试场次平均减少一场，减少40%的试卷计算。年四次考试节。个院校每年考试节约费用教师出试卷印刷制版监考老师费用成本00个考试点全国六十多所院梭可 以节约的费用1、772000每次考试10万人次19300

7、0（例如：一人一次参加六门考试算6人次）23160000优化考试排程节约费用表（单位:元）60000oooo1叫元*1叩份=10000400001200000=1000001DCI 元*1000 场, , ,考场场地综合:.:.: : ：.： j-J： y. .LJJ页.用 X XXX Xv： XX XX XX XX XX XX XX XX 就 XX XX XX XX XX XX XX XX Ji40000012000000.: . ,: Z60 元*1CICICI 场=6000024000072000008000%32000960000疲元*1叩份=15000计算依据2、教室租金每天每间20

8、0元3、监考费用每场60元（两人）4、教室最少按半天租金算5、考试科目1406、手工排程平均一次考试考卷数量2507、优化排程平均减少40%的试卷数量，8、优化排程考试场次平均减少一场9、手工编排一次考试计划需要四个人一周的工作量从分析表格看出，优化排程可以节约非常巨大的经费。当然，由于我国远程教育系统的学费收支系统、各个网络学院的网络体系的建设以及收支方式的不同，一些减少（节省）的费用不一定能让学 院得到实惠。但是，不管最终节省的费用落到谁的手里，-LSA2S节省了资源，减少了费用是一个确定的事实。从社会效益来说，网络学院的学生大部分分散在各个地方，参加一次考试，往往要在路途奔波，要在考场附近解决食宿。如果我们减少的考试 场次，节约了时间，对于学校和对于考生都是非常有益的。在本案中，采用市场流行的标准配置服务器，大约在10-30分钟的运算就可以得到一个很不错的排程结果，运行一到两个小时可以得到唯一的 最佳结果。两者相差不大，无非是多一两份考卷的差别。需要海量迭代的优化运算似乎不可能采用“常驻内存”的算法。我希望请教网络中常说的“常驻内存”的算法是怎么回事？也不明白有些APS 能够在几秒钟得到优化