这个问题的领域是在受限硬件上调度操作。结果的分辨率是时间表适合的时钟周期数。搜索空间增长非常迅速，早期的决策限制了未来的决策，并且可能的调度总数快速且呈指数增长。许多可能的调度是等价的，因为仅仅交换两条指令的顺序通常会导致相同的时序约束。
基本上，问题是在不花费太多时间的情况下探索广阔的搜索空间的好策略是什么。我希望只搜索一小部分，但希望在这样做的同时探索搜索空间的不同部分。
当前的贪心算法有时会在早期做出愚蠢的决定，并且分支定界的尝试速度非常慢。
编辑：想要指出结果是非常二元的，可能贪心算法最终使用 8 个周期，而存在使用分支定界仅使用 7 个周期的解决方案。
第二点是指令之间的数据路由和指令之间的依赖关系有很大的限制，这限制了解决方案之间的通用性。将其视为具有大量排序约束的背包问题以及由于路由拥塞而完全失败的一些解决方案。
澄清：在每个循环中，每种类型的操作数量都有限制，并且某些操作有两种可能的类型。有一组路由约束可以变化为相当严格或相当宽容，并且限制取决于路由拥塞。
NP-hard问题的整数线性优化
根据您的侧面约束，您可能能够使用关键路径方法或（如上一个答案中所建议的）动态编程。但是许多调度问题是 NP 难题，就像经典的旅行推销员一样——精确的解决方案具有指数搜索时间的最坏情况，正如您在问题中所描述的那样。
重要的是要知道，虽然 NP-hard 问题仍然有一个非常糟糕的最坏情况解决时间，但有一种方法通常可以通过非常短的计算产生准确的答案（平均情况是可以接受的，你通常看不到最坏的情况） .
这种方法是将您的问题转换为具有整数变量的线性优化问题。有免费软件包（例如 lp-solve）可以有效地解决这些问题。
这种方法的优点是它可以在可接受的时间内为您提供 NP-hard 问题的准确答案。我在一些项目中使用了这种方法。
由于您的问题陈述不包含有关侧面约束的更多详细信息，因此我无法详细说明如何应用该方法。
编辑/添加：示例实现
以下是有关如何在您的情况下实施此方法的一些详细信息（当然，我做了一些可能不适用于您的实际问题的假设——我只知道您问题的详细信息）：
假设您有 50 条指令 cmd(i) (i=1..50) 被安排在 10 个或更少的周期 cycle(t) (t=1..10) 内。我们引入了 500 个二进制变量 v(i,t) (i=1..50; t=1..10)，它们表示指令 cmd(i) 是否在周期 (t) 执行。这个基本设置给出了以下线性约束：
v_it integer variables
0<=v_it; v_it<=1; # 1000 constraints: i=1..50; t=1..10
sum(v_it: t=1..10)==1 # 50 constraints: i=1..50
现在，我们必须指定您的附加条件。假设操作 cmd(1)...cmd(5) 是乘法运算，并且您恰好有两个乘法器 --- 在任何循环中，您最多可以并行执行其中两个操作：
sum(v_it: i=1..5)<=2 # 10 constraints: t=1..10
对于每个资源，您需要添加相应的约束。
另外，假设操作 cmd(7) 依赖于操作 cmd(2) 并且需要在它之后执行。为了使方程更有趣，我们还需要它们之间的两个周期间隙：
sum(t*v(2,t): t=1..10) + 3 <= sum(t*v(7,t): t=1..10) # one constraint
注意： sum(t*v(2,t): t=1..10) 是循环 t，其中 v(2,t) 等于 1。
最后，我们希望最小化周期数。这有点棘手，因为您按照我建议的方式获得了相当大的数字：我们为每个 v(i,t) 分配一个随时间呈指数增长的价格：将操作推迟到未来比尽早执行要昂贵得多：
sum(6^t * v(i,t): i=1..50; t=1..10) --> 最小值。# 一个目标函数
我选择 6 大于 5 以确保向系统添加一个周期比将所有内容压缩成更少的周期更昂贵。一个副作用是程序会尽可能早地安排操作。您可以通过执行两步优化来避免这种情况：首先，使用这个目标函数来找到最少的必要循环数。然后，用不同的目标函数再次问同样的问题 --- 一开始就限制可用周期的数量，并为以后的操作施加更温和的价格惩罚。你必须玩这个，我希望你明白了。
希望您可以将所有要求表达为二进制变量中的线性约束。当然，可能有很多机会可以利用您对特定问题的洞察力来减少约束或减少变量。
然后，将您的问题交给 lp-solve 或 cplex，让他们找到最佳解决方案！
乍一看，听起来这个问题可能适合动态规划解决方案。多个操作可能会花费相同的时间，因此您最终可能会遇到重叠的子问题。
如果您可以将您的问题映射到“旅行推销员”（例如：找到在最短时间内运行所有操作的最佳序列），那么您就有一个 NP 完全问题。
解决这个问题的一个非常快速的方法是蚂蚁算法（或蚁群优化）。
这个想法是你在每条路径上都派一只蚂蚁。蚂蚁在路径上散布有气味的物质，随着时间的推移会蒸发。较短的部分意味着当下一只蚂蚁出现时，这条路会更臭。蚂蚁更喜欢臭而不是干净的路径。通过网络运行成千上万的蚂蚁。最臭的路径是最佳路径（或至少非常接近）。
尝试模拟退火，cfr。http://en.wikipedia.org/wiki/Simulated_annealing。