一个有点难度的算法

现有N个实习小组，要进行一产品生产工序操作的学习，该产品有M个工序，各工序有各自的实习要求时间（连续I周）及同时允许J个小组实习，在实习期间（总时间根据M[1]*I[1]+M[2]*I[2]+…+M[x]*I[x]）得到，小组数据N不能大于各工序所能允许小组数量的总和(M[1]*J[1]+M[2]*J[2]+…+M[x]*J[x]))。要求各小组在实习期间必须各个工序都要进行学习。请教这种情况的排班算法
提供思路即可,如能提供主要算法的代码那是最好不过

解决方案 »

免费领取超大流量手机卡，每月29元包185G流量+100分钟通话, 中国电信官方发货

我不知道是我太驽钝还是楼主的表述有问题。M个工序，那么我的理解M就是一个数，可是后面M又变成了数组其他标识符也是一样的问题
有N个小组M个工序，p[i]表示第i工序所需的时间，q[i]表示第i工序最大组数。按我的理解这里的N，M，p[i]，q[i]（i＝1，2...M）都是常数。至于楼主的公式我看不明白，烦请解释一下？
可能我表述有点问题以楼上的表述，有N小组，M个工序,p[i]表示第i工序所需的时间,q[i]表示第i工序允许的最大组数
实习总时间是p[1]+p[2]+...+p[M]
其中N<=q[1]+q[2]+..+q[M]现在要求就要实习总时间内完成各个小组的安排
实习总时间是 p[1]+p[2]+...+p[M]
不允许超过，如果超过的话认为是无法完成的排班
你那M个工序有先后顺序吗？是必须完成了第一个才能开始第二个，还是任意的，只要最终能完成所有工序就行？还有一点不明白的就是楼主说“实习总时间是 p[1]+p[2]+...+p[M]
不允许超过，如果超过的话认为是无法完成的排班”而每个小组又是每个工序都要做，而且每个工序固定的时间就是p[i]，那么计算出来的固定小组实习的最短时间岂不都是p[1]+p[2]+...+p[M]了？
小组实习的最短时间的确是p[1]+p[2]+...+p[M]
最主要是怎么样去安排，使得各小组都能在这段时间内实习完成
线性规划下面有个ppt，你可以看看http://www.51ppt.com.cn/Soft/ShowSoftDown.asp?UrlID=1&SoftID=277
好像设计到两个量的考虑，一个是要分成N内的几个组如M 个（M<=N)，一个是这M个组如何排班使学习时间最短。
所以要解决问题，先要确定组数啊，如果就一个组，那么时间肯定最少了，也不用排了！
不知道我的描述是否正确？
不过，如果M分别取[1,n]中的不同值对于不同M应该有相应解，考虑先！
此题应还有限制或放松限制，在目前这种要求，存在无解情况.
如4组2道工序，第一道工序最大1组，第二道工序最大6组而且两道工序时间一样那么
时间最少为4p[1]而非p[1]+p[2]=2[p1]
因此我感觉只能求排班最少时间，而且这还和具体每一道工序时间有关系。
比如N=3,M=2,q[1]=1,q[2]=4情况1：p[2]=p[1]
那么显见最小时间为3p[1]情况2：p[2]=2[p1]
那么显见最小时间为2p[2]=4[p1]也不为p[1]+p[2]=3p[1]总之干感觉到想在p[1]+...+p[M]内完成纯属痴心妄想
实际上上述可以转化为下述模型
求数组
  I[1,1] I[1,2] ... I[1,K]
  I[2,1] I[2,2] ... I[2,K]
   ...    ...   ...  ...
  I[N,1] I[N,2] ... I[N,K]其中
  1.K=一共要排K次班,K>=M
  2.I[i,j]为第i组第j班正在执行的工序。取值0..M,0代表轮空。
  3.对每一行I[i,1]...I[i,K] 必须包含所有的0..M，I[i,m]...I[i,n](m..n为连续的属于1..K的子集)可以相同,但在这一组中除0外只能重复出现一次。
  4.对每一列I[1..j]...I[N..j] 必须满足它所有取的不同的值m的重复个数R[m]应<=m工序允许的最大组数q[m]使得
  N组中完成工序所需最长的时间最小
限制条件太少，是没有排序算法的。假设反推即可：设有两个工序:
M1=(1天,1人)
M2=(2天,2人)那么
最多安排人<= 3人
最多安排天<= 3天穷举：
第一天：1人M1,2人M2
第二天：1人M1,2人M2
第三天：1人M1,2人M2
----------------------
合计：  3人   6人似乎是可以的，但实际上第二天的做M1的人是把M2的两天拆分开才完成M2的。如果不允许没完成一个工序就去做另一个工序，那么这显然是不可能的。因此没有算法。