多目标问题的图表示
我正在调查一个涉及多目标调度问题的论文项目的可能研究主题，我想知道是否有人有将此类问题表示为图表的想法。我看过一些关于该主题的文献，一种常见的方法似乎是在边缘使用成本向量而不是单个成本数。这对我来说很有意义，但我不知道如何以这种方式对问题的某些方面进行建模。
特别是，模型中的某些资源将每个活动限制在特定的时间窗口内，并且有效的计划必须在这些限制内安排每个活动。此外，还有一些相互依赖的活动集。例如，用户可以在两个活动之间设置时间增量要求，表示它们必须在彼此的一定数量的时间单位内进行安排，或者必须在有效的计划中至少相隔一定数量的时间单位。我可以想象将它们建模为成本向量中的可选元素，但有更好的方法吗？
额外的问题是，这也应该是最少承诺调度程序。每个活动都应该有一个名义上为 n 个时间单位长的窗口，因此活动不一定有总顺序。
任何有关表示此类问题的文献将不胜感激！
I'm investigating a possible research topic for a thesis project that involves a multi-objective scheduling problem and I'm wondering if anyone has ideas for representing such a problem as a graph. I've looked at some literature on the subject and a common approach seems to be using cost vectors on the edges instead of a single cost number. This makes sense to me but I don't see how I can model certain aspects of my problem this way.
In particular there are resources in the model that constrain each activity to certain time windows and a valid schedule must schedule each activity within these constraints. Further, there are some sets of activities that are dependent on each other. For example a user can place time delta requirements between two activities saying they must be scheduled within some number of time units of each other or must be at least some number of time units apart in a valid schedule. I can imagine modeling these as optional elements in a cost vector but is there a better way?
Bonus question is that this is also supposed to be a least commitment scheduler. Each activity should be given some window that's nominally n time units long so there doesn't have to necessarily be a total order on activities.
Any literature on representing problems like this would be much appreciated!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这里有一个关键字可供您搜索：约束编程
您可以对此类问题进行建模，例如所谓的约束满足问题，即一堆变量、它们的可能值以及您的解决方案所需要的一组约束（ =变量值的选择）必须满足。
使用 CP，您可以直接将上面的文本表述为单独的约束（例如，活动 A 必须先于活动 B 变为 A.endTime <= B.startTime 之类的内容）。
至于文献，有大量关于 CP 的书籍和论文，尤其是关注调度的书籍和论文（甚至有一个专门针对调度问题的 CP 会议）。
Here's a keyword for you to search for: Constraint Programming
You can model such problems as so-called constraint satisfaction problems, i.e. a bunch of variables, their possible values, and a set of constraints that your solution (=selection of values for the variables) has to satisfy.
With CP you can directly formulate your text above as individual constraints (f.ex., activity A has to be before activity B becomes something like A.endTime <= B.startTime).
As for literature, there are loads of books and papers on CP available, especially with a focus on scheduling (there's even a conference dedicated to CP for scheduling problems).
听起来像作业车间调度：有很多关于这方面的文章。
Sounds like Job Shop Scheduling: there are plenty of articles on that.