发帖
雷达卡
摘要翻译：
本文研究了单机总加权延误问题(SMTWTP)的一种较为简单的局部搜索启发式，即爬山和变邻域搜索。特别是，我们重新审视SMTWTP的这些方法，因为在这种情况下，似乎缺乏适当的/具有挑战性的基准实例。所取得的结果确实令人印象深刻。只有很少的实例仍未解决，甚至那些近似于最优/最已知解的1%之内。我们的实验支持了SMTWTP的元启发式方法很有可能导致好的结果的说法，并且在改进搜索策略之前，必须对基准数据的提出做更多的工作。从我们的调查中得出了一些关于构建此类数据集的建议。
---
英文标题：
《The Single Machine Total Weighted Tardiness Problem - Is it (for
Metaheuristics) a Solved Problem ?》
---
作者：
Martin Josef Geiger
---
最新提交年份：
2009
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要：
The article presents a study of rather simple local search heuristics for the single machine total weighted tardiness problem (SMTWTP), namely hillclimbing and Variable Neighborhood Search. In particular, we revisit these approaches for the SMTWTP as there appears to be a lack of appropriate/challenging benchmark instances in this case. The obtained results are impressive indeed. Only few instances remain unsolved, and even those are approximated within 1% of the optimal/best known solutions. Our experiments support the claim that metaheuristics for the SMTWTP are very likely to lead to good results, and that, before refining search strategies, more work must be done with regard to the proposition of benchmark data. Some recommendations for the construction of such data sets are derived from our investigations.
---
PDF链接：
https://arxiv.org/pdf/0907.2990
京公网安备 11010802022788号
