论文部分内容阅读
目前，求解组合优化问题的研究主要分为算法的研究和经验性的实验研究。算法研究致力于函数的优化，建立数学模型并设计相应的算法，这一领域吸引了众多学者；而实验研究是在已有算法的基础之上，设计大量的实验，用统计的方法，通过评价参数、解决质量、运行时间等多项指标来对某几个算法进行比较和讨论。
本课题将通过实验寻找并验证一类时间相关组合优化问题的高效解决途径。这类问题设定了一组在连续不间断的时间单元内依次进行的任务，和一组完成任务的工人及其在不同时间单元内完成不同任务的开销，并且限定：一个工人能够竞标多个任务，但最终被分配所得的任务不得多于一个，力求找到一个合理分配任务的最优解。这类问题本身对于解决更复杂问题具有现实意义，同时也为对不同的解决方法之间的解决质量及其时间复杂度进行更加客观的比较提供了一个平台。
由于当前学术领域内开展的实验比较研究并不像函数优化研究那样普遍，并且主要集中于TSP等更为经典的问题，而对这一类时间相关问题的研究本身便不多见。所以，本课题选择对该类问题进行实验比较研究，具有很大的学术意义。
该研究涉及遗传算法、模拟退火、随机扫描策略等多种算法。经过大量的实验，结果表明，遗传算法和模拟退火对于该类时间相关的组合优化问题，分别在运行时间和求解质量方面有较好的效果。