1、在厨房里面有4个炉子，需要不断的利用这些炉子来制作蛋糕
2、每个蛋糕有N个制作步骤，每个步骤都需要进炉子烘烤一段时间
3、每个烘烤步骤完成后，都需要将蛋糕放置一个时间段后，才能进炉子进行下个步骤
4、每种蛋糕的制作步骤都是不同的，需要在炉子中呆的时间也不一样，等待时间也不一样
5、有N种蛋糕准备要入炉
现在业务经理开始安排下个月要制作的所有的蛋糕，需要一个程序来自动将逐个插入的蛋糕进行排列，使炉子的利用用率最高
在线急等！ 有任何不清楚的请加7009017讨论，万分感谢！！
8 个解决方案
#1
你这个是运筹学的基本东西,可以看看排队论的书
#2
安？？ 哥们，我今天要交货，怕是没时间看运筹学了.....你有没有思路？给我提一下嘛
#3
玄
#4
学过操作系统没？
炉子是CPU同时可进行四个任务。
蛋糕是任务，每次运行需要一个CPU资源。
当蛋糕运行一段时间后，需要等待其它事件。
如果问题是仅仅关心CPU的效率。那么事情简单。使用长作业优先就可以了。
但问题是有可能最短的任务会被一直压着。而不能得到执行。
首先，任务分为三种情况，等待，就绪，运行。
等待：任务需要等待一定事件能才转入就绪。
就绪：任务完成所有等待的事件只要得到CPU就能运行。
运行：正在占用CPU并在结束后转入等待状态。
那么改良的算法：
首先是任务排队，选出就绪的任务，最长的任务进CPU。
运行。（这其间会有任务从等待状态转为就绪状态）
然后当某CPU资源空闲时，计算就绪状态队列的响应值。
需要运行时间 * (已经等待时间 + 1)。
那么我们选择的应当是这个值尽量的大的任务。
(反过来应用的响应比优先算法)
基本思路就是这个，那个公式可以改改，因为你的蛋糕的因等待而需要优先的比值是不一定的，你可以增加一个量来提高或降低，最后响应值中的时间所占份额。
炉子是CPU同时可进行四个任务。
蛋糕是任务，每次运行需要一个CPU资源。
当蛋糕运行一段时间后，需要等待其它事件。
如果问题是仅仅关心CPU的效率。那么事情简单。使用长作业优先就可以了。
但问题是有可能最短的任务会被一直压着。而不能得到执行。
首先，任务分为三种情况，等待，就绪，运行。
等待：任务需要等待一定事件能才转入就绪。
就绪：任务完成所有等待的事件只要得到CPU就能运行。
运行：正在占用CPU并在结束后转入等待状态。
那么改良的算法：
首先是任务排队，选出就绪的任务，最长的任务进CPU。
运行。（这其间会有任务从等待状态转为就绪状态）
然后当某CPU资源空闲时，计算就绪状态队列的响应值。
需要运行时间 * (已经等待时间 + 1)。
那么我们选择的应当是这个值尽量的大的任务。
(反过来应用的响应比优先算法)
基本思路就是这个，那个公式可以改改，因为你的蛋糕的因等待而需要优先的比值是不一定的，你可以增加一个量来提高或降低，最后响应值中的时间所占份额。
#5
同意楼上说法，最主要是你要先划分清楚各个状态，蛋糕有多少个状态，炉子有空闲、忙两个状态，用运筹学方法，将蛋糕排队，顺序放入，最后用穷举法求出各个方案的时间，找出最短时间。
呵呵，真的很复杂，我也只能想到这么多，具体实现，我想你可以将时间做为一个重要变量，每个蛋糕分两个时间：等待时间和烘烤时间，然后，每一步里，将时间累加
呵呵，真的很复杂，我也只能想到这么多，具体实现，我想你可以将时间做为一个重要变量，每个蛋糕分两个时间：等待时间和烘烤时间，然后，每一步里，将时间累加
#6
补充一下吧，我的算法是建立在“在事先不知道运行后的等待时间”的前题下。
改良一下公式：
需要运行时间 * ((已经等待时间 * n) + 1)。
这里n的取值小于1 时可以减少时间在提高执行顺序中的比重，大于1时则反之。
改良一下公式：
需要运行时间 * ((已经等待时间 * n) + 1)。
这里n的取值小于1 时可以减少时间在提高执行顺序中的比重，大于1时则反之。
#7
其实这个跟操作系统中的进程算法差不多,采用操作系统里面的最佳响应比算法就行了.
#8
不好意思啊，我把大家带沟里去了。吃了个饭，想了想用不着那么麻烦。
按以下原则排序就行了。
Ａ：运行后等待时间越短，越优先执行。
(如果出现空闲，等待时间最短的是最先完成，所以空闲时间也就是最短)
Ｂ：运行步骤越多的，越优先执行。
(运行的任务越少，那么出现空闲的机会就越大，所以要平衡各任务间的运行进度)
问题就在于二个原则是有冲突的，如何在Ａ原则和Ｂ原则间转化。
先按Ａ原则计算队列，然后得出最后执行的任务[P(lost)]的完成时间[t(f)]和等待[t(w)]的时间。
设：Tr = P(lost).t(f) + P(lost).t(w) - NOW();
然后计算等待队列在时间T内可以转为就绪的任务运行时间总量：Tw。
如果：Tr : Tw 的值大于1那么按B原则挑选任务。
这样比响应比算法简单很多。最后的Tr : Tw比值是算法的关键，互相转化的点不一定是1，我只是给出算法，那个数我也没想好，你作作试验吧。
按以下原则排序就行了。
Ａ：运行后等待时间越短，越优先执行。
(如果出现空闲，等待时间最短的是最先完成，所以空闲时间也就是最短)
Ｂ：运行步骤越多的，越优先执行。
(运行的任务越少，那么出现空闲的机会就越大，所以要平衡各任务间的运行进度)
问题就在于二个原则是有冲突的，如何在Ａ原则和Ｂ原则间转化。
先按Ａ原则计算队列，然后得出最后执行的任务[P(lost)]的完成时间[t(f)]和等待[t(w)]的时间。
设：Tr = P(lost).t(f) + P(lost).t(w) - NOW();
然后计算等待队列在时间T内可以转为就绪的任务运行时间总量：Tw。
如果：Tr : Tw 的值大于1那么按B原则挑选任务。
这样比响应比算法简单很多。最后的Tr : Tw比值是算法的关键，互相转化的点不一定是1，我只是给出算法，那个数我也没想好，你作作试验吧。
#1
你这个是运筹学的基本东西,可以看看排队论的书
#2
安？？ 哥们，我今天要交货，怕是没时间看运筹学了.....你有没有思路？给我提一下嘛
#3
玄
#4
学过操作系统没？
炉子是CPU同时可进行四个任务。
蛋糕是任务，每次运行需要一个CPU资源。
当蛋糕运行一段时间后，需要等待其它事件。
如果问题是仅仅关心CPU的效率。那么事情简单。使用长作业优先就可以了。
但问题是有可能最短的任务会被一直压着。而不能得到执行。
首先，任务分为三种情况，等待，就绪，运行。
等待：任务需要等待一定事件能才转入就绪。
就绪：任务完成所有等待的事件只要得到CPU就能运行。
运行：正在占用CPU并在结束后转入等待状态。
那么改良的算法：
首先是任务排队，选出就绪的任务，最长的任务进CPU。
运行。（这其间会有任务从等待状态转为就绪状态）
然后当某CPU资源空闲时，计算就绪状态队列的响应值。
需要运行时间 * (已经等待时间 + 1)。
那么我们选择的应当是这个值尽量的大的任务。
(反过来应用的响应比优先算法)
基本思路就是这个，那个公式可以改改，因为你的蛋糕的因等待而需要优先的比值是不一定的，你可以增加一个量来提高或降低，最后响应值中的时间所占份额。
炉子是CPU同时可进行四个任务。
蛋糕是任务，每次运行需要一个CPU资源。
当蛋糕运行一段时间后，需要等待其它事件。
如果问题是仅仅关心CPU的效率。那么事情简单。使用长作业优先就可以了。
但问题是有可能最短的任务会被一直压着。而不能得到执行。
首先，任务分为三种情况，等待，就绪，运行。
等待：任务需要等待一定事件能才转入就绪。
就绪：任务完成所有等待的事件只要得到CPU就能运行。
运行：正在占用CPU并在结束后转入等待状态。
那么改良的算法：
首先是任务排队，选出就绪的任务，最长的任务进CPU。
运行。（这其间会有任务从等待状态转为就绪状态）
然后当某CPU资源空闲时，计算就绪状态队列的响应值。
需要运行时间 * (已经等待时间 + 1)。
那么我们选择的应当是这个值尽量的大的任务。
(反过来应用的响应比优先算法)
基本思路就是这个，那个公式可以改改，因为你的蛋糕的因等待而需要优先的比值是不一定的，你可以增加一个量来提高或降低，最后响应值中的时间所占份额。
#5
同意楼上说法，最主要是你要先划分清楚各个状态，蛋糕有多少个状态，炉子有空闲、忙两个状态，用运筹学方法，将蛋糕排队，顺序放入，最后用穷举法求出各个方案的时间，找出最短时间。
呵呵，真的很复杂，我也只能想到这么多，具体实现，我想你可以将时间做为一个重要变量，每个蛋糕分两个时间：等待时间和烘烤时间，然后，每一步里，将时间累加
呵呵，真的很复杂，我也只能想到这么多，具体实现，我想你可以将时间做为一个重要变量，每个蛋糕分两个时间：等待时间和烘烤时间，然后，每一步里，将时间累加
#6
补充一下吧，我的算法是建立在“在事先不知道运行后的等待时间”的前题下。
改良一下公式：
需要运行时间 * ((已经等待时间 * n) + 1)。
这里n的取值小于1 时可以减少时间在提高执行顺序中的比重，大于1时则反之。
改良一下公式：
需要运行时间 * ((已经等待时间 * n) + 1)。
这里n的取值小于1 时可以减少时间在提高执行顺序中的比重，大于1时则反之。
#7
其实这个跟操作系统中的进程算法差不多,采用操作系统里面的最佳响应比算法就行了.
#8
不好意思啊，我把大家带沟里去了。吃了个饭，想了想用不着那么麻烦。
按以下原则排序就行了。
Ａ：运行后等待时间越短，越优先执行。
(如果出现空闲，等待时间最短的是最先完成，所以空闲时间也就是最短)
Ｂ：运行步骤越多的，越优先执行。
(运行的任务越少，那么出现空闲的机会就越大，所以要平衡各任务间的运行进度)
问题就在于二个原则是有冲突的，如何在Ａ原则和Ｂ原则间转化。
先按Ａ原则计算队列，然后得出最后执行的任务[P(lost)]的完成时间[t(f)]和等待[t(w)]的时间。
设：Tr = P(lost).t(f) + P(lost).t(w) - NOW();
然后计算等待队列在时间T内可以转为就绪的任务运行时间总量：Tw。
如果：Tr : Tw 的值大于1那么按B原则挑选任务。
这样比响应比算法简单很多。最后的Tr : Tw比值是算法的关键，互相转化的点不一定是1，我只是给出算法，那个数我也没想好，你作作试验吧。
按以下原则排序就行了。
Ａ：运行后等待时间越短，越优先执行。
(如果出现空闲，等待时间最短的是最先完成，所以空闲时间也就是最短)
Ｂ：运行步骤越多的，越优先执行。
(运行的任务越少，那么出现空闲的机会就越大，所以要平衡各任务间的运行进度)
问题就在于二个原则是有冲突的，如何在Ａ原则和Ｂ原则间转化。
先按Ａ原则计算队列，然后得出最后执行的任务[P(lost)]的完成时间[t(f)]和等待[t(w)]的时间。
设：Tr = P(lost).t(f) + P(lost).t(w) - NOW();
然后计算等待队列在时间T内可以转为就绪的任务运行时间总量：Tw。
如果：Tr : Tw 的值大于1那么按B原则挑选任务。
这样比响应比算法简单很多。最后的Tr : Tw比值是算法的关键，互相转化的点不一定是1，我只是给出算法，那个数我也没想好，你作作试验吧。