请教个算法，也欢迎大家来讨论(200分)

寂

寂寞的鸭子

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-08-30

• #1

最近碰到一个这样的需求，有车A台，司机B人，乘务员C人（每台车配司机和乘务员1名），车队根据车的台数排班次，也就是说有A台车则就有A个班次，客户希望有个好的算法，可以自动排班，尽量让每个司机和乘务员在最短的时间内遍历每个班次，并且司机和乘务员也尽量不要重复搭配（目的是为了防止司机和乘务员长时间在一起，容易作弊）。
已知条件：
1 B肯定是大于A的，C肯定是大于等于B的
2 因为司机比车多，所以每天会有B-A个司机安排休息，C-A个乘务员休息

请大家帮下忙，先谢谢了

 

Z

zywcd

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-08-30

• #2

procedure TForm1.Button1Click(Sender:TObject);
var a,b,c,k:integer;
ano,bno,cno:integer;
begin
ano:=5;//假设5部车
bno:=8
//8个司机
cno:=12
//12个售票员
a:=0;b:=0;c:=0;
for k:=1 to 100 do //排100次车
begin
Inc(a);
Inc(b);
Inc(c);
if a>ano then a:=1;
if b>bno then b:=1;
if c>cno then c:=1;
ListBox1.Items.Add('a:'+inttostr(a)+'b:'+inttostr(b)+'c:'+inttostr(c));
end;
end;
另外， 如果收票员和司机相等，你可以随机调整开始计数的位置。比如一天，或者几天以后重新排，那么可以使用随机数调整开始位置，这样很容易搭乱排序的。

 

Y

yuzk2005

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-08-30

• #3

to 楼上:
如果司机是车的倍数或售票员是司机的倍数,那么就不符合条件了,修改一下:
procedure TForm1.Button1Click(Sender:TObject);
var a,b,c,k:integer;
ano,bno,cno:integer;
begin
ano:=5;//假设5部车
bno:=8
//8个司机
cno:=12
//12个售票员
a:=0;b:=0;c:=0;
for k:=1 to 100 do //排100次车
begin
Inc(a);
Inc(b);
Inc(c);
if a>ano then a:=1;
if b>bno then begin
b:=1;
if bno mod ano=0 then
b:=2;
end;
if c>cno then begin
c:=1;
if cno mod bno=0 then
c:=2;
end;

ListBox1.Items.Add('a:'+inttostr(a)+'b:'+inttostr(b)+'c:'+inttostr(c));
end;
end;

 

Z

zywcd

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-08-30

• #4

呵呵，对的。谢谢。确实需要考虑种子问题。

 

寂

寂寞的鸭子

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-08-30

• #5

可能是我没有描述清楚，这样吧，举个具体的例子，假设有3台车，4个司机（S1-S4），4个乘务员（C1-C4）。以前车队可能会手工这样排班，总之是为了满足这样的条件：
在最短的时间内：司机上不同班次的班，同时不和以前搭配的乘务员再在一起，刚刚忘了还有一个条件，就是前一天休息的人第二天必须上班
班次1 班次2 班次3 休息
第一天的排班： S1＋C1 S2＋C2 S3＋C3 S4＋C4
第二天的排班： S4＋C2 S1＋C4 S2＋C1 S3＋C3
第三天的排班： S3＋C4 S4＋C3 S1＋C2 S2＋C1
第四天的排班： S2＋C3 S3＋C1 S4＋C4 S1＋C2
然后开始下一个循环，重复上面的操作了
第五天的排班： S1＋C1 S2＋C2 S3＋C3 S4＋C4
不知道这样说明白了没，其实就是一个公交车队的排班工作。因为不同时间段（实际上就是班次）的客流量是不一样的，而客流量又是和司机、乘务员的收入挂钩的，所以为了公平，在最短的时间内让司机和乘务员遍历每个班次。

 

D

d5love

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-08-30

• #6

应该保证司机和司机之间上班的频率和时间段都要公平
还有乘务员也要一样呀

 

C

cqwty

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-08-30

• #7

建议你看看图论里面的匹配问题，这个就是那个问题的一个例子了！

 

寂

寂寞的鸭子

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-08-31

• #8

说实话，图论看过，实在没看懂，不可能为了这个算法让我把整个图论算法与程序设计啃下来吧。我只想解决这个问题，有会的朋友还望不吝赐教。

 

C

cqwty

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-08-31

• #9

其实不要你怎么看的了，你就看图论里面的匹配问题这点就可以了，我主要是身边没有图论的书籍，原来学的，因为没有用，所以忘了。不好意思！

 

寂

寂寞的鸭子

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-09-01

• #10

呵呵，算了，我试试用个笨方法去实现，谢谢楼上几位的热心帮助。