制定具有非线性约束的优化问题

Question

我正在尝试使用我认为符合非线性编程约束的内容来解决动态机器调度问题。

我拥有线性编程技术的学术知识，并很高兴有机会尝试非线性编程。

然而，在做任何事情之前，我都在努力写下一个精心讨论的问题。情况是这样的：

• 我有一个按“紧急程度”排序的各种性质的任务列表
• 专门从事各种任务的几台机器，根据“紧急程度”及其专业来处理这些任务
• 任务不是抢占式的（开始一项，完成它，不间断）
• 根据任务的性质和分配给它的机器，统计上可以知道完成时间。
• 所有机器的使用应尽量减少停机时间
• 工作负载均衡：机器处理大致相同数量的任务，并且工作总时间也相同

你能帮我正确地表述这个问题吗？这是我开始的方式：

• M 台机器
• S个专业
• 
• T 组任务中的 t
• 
• 机器完成任务 t 的时间 m
• 任务 t 延迟超过可接受时间开始的惩罚系数
• X_mt 1 如果任务 t 分配给机器 m 0 否则

目标函数： 找到最佳 X_mt，使任务按时开始（限制惩罚）

限制：

• 工作时间通过机器进行平衡（epsilon 是一个参数）：

• 工作项目的数量通过机器进行平衡（epsilon 是一个参数）：

• 机器选择它擅长的任务（点积m专业/t特征）

• 最小化完工时间

• 每台机器仅分配 1 个任务

我也在寻找一种算法，根据我如何放松工作负载平衡参数来找到一些 epsilon 最优解决方案。

但是在我尝试寻找算法之前，我需要帮助来正确地表述问题。

我见过示例，其中方差约束被公式化为上下边界差异的最小化，但我不知道如何在这种情况下应用它，因为我有多个方差约束。

如果这太多了，你如何将这个问题转化为强化学习问题？

Answer 1

其中一个要求是尽量减少机器之间作业数量和工作时间方面的差异。

所以我有两个差异正在努力最小化。正如您所提到的，最小化每个方差的跨度更容易。 我们将工作数量的方差称为

var1

和工作时间的方差

var2

。 它们的跨度分别是

max1-min1

和

max2-min2

。

我永远不会找到工作到机器的最佳归因，其中两个方差的方差都是最低的（除非我非常幸运并且它们的最小值恰好同时存在：https://math.stackexchange.com/a /452561）.

所以我应该在两个方差之间提供权衡（epsilon）和权重（

w1

和

w2

）。

所以我的目标函数变成

MINIMIZE sum(p_t) + w1 * (max1 - min1) + w2 * (max2 - min2)

这种情况下，如何找到w1和w2呢？蒙特卡洛？模拟退火？机器学习？ 难道我理解错了？