排班算法，很现实，哪个单位都会用得着，高手相送5000分

Question

a1,a2,a3,a4,a5
b1,b2,b3,b4,b5,
c1,c2,....
...
==>
编排成每天四人一组:a1,b1,c1,d1
如果a1,c3,不在则
==>a2,b1,c1,d1
a3,b2,c2,d2
a4,b3,c4,d3
a5,b4,c5,d4
回来后进入队列等待排班就行,不用优先
明白不,
a,b,c,d,e,f,g,h依次顺序有八个处,
每个处有3-12人不等
处内循环
工作日周一至五排一班,
要记录上周各处排到的最后一个人a4,b5,c8,d6..及周五第4个人所在处室a,本周先确定在位人员后接着轮换b6,c9,d7...

Answer 1

lizhongkun 您好
 
剩余可用分：5585
总技术分：3505
总非技术分：141
现在排名：6259
上次排名：6253 麻烦版主推荐置顶一下,我以前也是版主的嘛 ,很久没来,改版了,也不知道是哪个版的版主了

Answer 2

描述还不是很到位。。
处内循环，是每天每个处都派一个人吗？但又说每天4人一组？是轮完abcd再轮efgh？
例外的a1,c3是怎么个规则也没有说清楚。

Answer 3

对,轮完abcd再轮efgh
每天轮换4个处,每个处依照处内顺序抽一个人
sorry ,现在说话不严谨了

Answer 4

各处人数也不相等啊,我感觉,楼主意思是,abcd,先轮完的,排e,然后次轮完的,排f,....

Answer 5

感觉不大对啊,楼主,abcd不可能同时轮完啊,肯定有先后的吧?
如果a的人数>b,那么b排完了,接来是是怎么处理的啊?

Answer 6

对,轮完abcd再轮efgh 
每天轮换4个处,每个处依照处内顺序抽一个人 
sorry ,现在说话不严谨了 
 
感觉不大对啊,楼主,abcd不可能同时轮完啊,肯定有先后的吧? 
如果a的人数>b,那么b排完了,接来是是怎么处理的啊?是抡过abcd4个处中分别抽了一个人后,就轮efgh4个处分别抽的1个人

Answer 7

//若是要为某处添加或删除值班人员，只需list[index].Add或remove相应的项。然后再调用GetData()        static void Main(string[] args)//调用
        {
            OnDuty();
        }        static void OnDuty()
        {
            List<List<string>> list = new List<List<string>>();
            List<string> listA = new List<string>(new string[] { "a1", "a2", "a3", "a4" });
            List<string> listB = new List<string>(new string[] { "b1", "b2", "b3" });
            List<string> listC = new List<string>(new string[] { "c1", "c2", "c3", "c4" });
            List<string> listD = new List<string>(new string[] { "d1", "d2", "d3", "d4", "d5" });
            List<string> listE = new List<string>(new string[] { "e1", "e2", "e3", "e4", "e5", "e6", "e7", "e8" });
            List<string> listF = new List<string>(new string[] { "f1", "f2", "f3", "f4" ,"f5"});
            List<string> listG = new List<string>(new string[] { "g1", "g2", "g3", "g4" ,"g5"});
            List<string> listH = new List<string>(new string[] { "h1", "h2", "h3" });
            list.Add(listA);
            list.Add(listB);
            list.Add(listC);
            list.Add(listD);
            list.Add(listE);
            list.Add(listF);
            list.Add(listG);
            list.Add(listH);
            int[] nextPos = new int[8];
            int dayCount = 25;
            GetData(list, nextPos, dayCount);
        }        static void GetData(List<List<string>> list, int[] nextPos, int dayCount)//daycount为输出多少天的值班
        {            int[] c1 = new int[4];
            int[] c2 = new int[4];
            for (int i = 0; i < 4; i++)
            {
                c1[i] = list[i].Count;
                c2[i] = list[i + 4].Count;
            }
            Array.Sort(c1);
            Array.Sort(c2);
            int count = 0;
            while (true)
            {
                for (int i = 0; i < c1[0]; i++)
                {
                    for (int j = 0; j < 4; j++)
                    {
                        Console.Write(list[j][nextPos[j]] + ",");
                        nextPos[j] = (nextPos[j] + 1) % list[j].Count;
                    }
                    count++;
                    if (count == dayCount) return;
                    Console.WriteLine();
                }
                for (int i = 0; i < c2[0]; i++)
                {
                    for (int j = 0; j < 4; j++)
                    {
                        Console.Write(list[j + 4][nextPos[j + 4]] + ",");
                        nextPos[j + 4] = (nextPos[j + 4] + 1) % list[j + 4].Count;
                    }
                    count++;
                    if (count == dayCount) return;
                    Console.WriteLine();
                }
            }
        }
/*输出：
a1,b1,c1,d1,
a2,b2,c2,d2,
a3,b3,c3,d3,
e1,f1,g1,h1,
e2,f2,g2,h2,
e3,f3,g3,h3,
a4,b1,c4,d4,
a1,b2,c1,d5,
a2,b3,c2,d1,
e4,f4,g4,h1,
e5,f5,g5,h2,
e6,f1,g1,h3,
a3,b1,c3,d2,
a4,b2,c4,d3,
a1,b3,c1,d4,
e7,f2,g2,h1,
e8,f3,g3,h2,
e1,f4,g4,h3,
a2,b1,c2,d5,
a3,b2,c3,d1,
a4,b3,c4,d2,
e2,f5,g5,h1,
e3,f1,g1,h2,
e4,f2,g2,h3,
a1,b1,c1,d3,
*/

Answer 8

没这么简单,我有一个生产排程的Demo的代码,如果觉得能用上的话,可以留下E_mail

Answer 9

        static void OnDuty()
        {
……
……
//假如两周后，c3出差，而h4回来
            int dayCount = 10;
            GetData(list, nextPos, dayCount);
Console.WriteLine();
list[2].Remove("c3");
list[7].Add("h4");
GetData(list, nextPos, dayCount);//继续排10天的班
        }//看下面的输出，10天后就没有c3了，而h4则出现了。
/*
a1,b1,c1,d1,
a2,b2,c2,d2,
a3,b3,c3,d3,
e1,f1,g1,h1,
e2,f2,g2,h2,
e3,f3,g3,h3,
a4,b1,c4,d4,
a1,b2,c1,d5,
a2,b3,c2,d1,
e4,f4,g4,h1,
a3,b1,c4,d2,
a4,b2,c1,d3,
a1,b3,c2,d4,
e5,f5,g5,h2,
e6,f1,g1,h3,
e7,f2,g2,h4,
e8,f3,g3,h1,
a2,b1,c4,d5,
a3,b2,c1,d1,
a4,b3,c2,d2,
*/

Answer 10

代码我没仔细看,看输出好像有问题,是否误解了排版规则,
没人不在位则第一,二天应该是:
a1,b1,c1,d1
e1,f1,g1,h1,
先轮换处,a->b->c->d->e->f->g->h->a->b.....
然后再在各处按照各处的顺序(a1->a2->a3->a4...)抽人确定
,  a2不在位由a3值
a处都不在由b处上周抽的那个人(若b11)的下一个(b12)开始排班
b12,c*,d*,e*
....
谢谢你很厉害，！再得5000分不知道是不是县太爷了！呵呵

Answer 11

这个只是好几种排班规则中的一种，还有几个更复杂的
min_jie这个用类似矩阵的方式循环非常聪明，再改一下应该就可以了，
我这太电脑没VS，明天test一下
再把另外几个复杂点的规则也贴出来供大家研究，

Answer 12

不好意思，是我没说清楚：
是抡过abcd4个处中分别抽了一个人后,就轮efgh4个处分别抽的1个人还有没有其他解法？？

Answer 13

//不知道这样是不是楼主要的：
/*输出：
a1,b1,c1,d1,
e1,f1,g1,h1,
a2,b2,c2,d2,
e2,f2,g2,h2,
a3,b3,c3,d3,
e3,f3,g3,h3,
a4,b1,c4,d4,
e4,f4,g4,h1,
a1,b2,c1,d5,
//此后b处所有人都不值班
e5,f5,g5,h2,
a2,c2,d1,e6,
f1,g1,h3,a3,
c4,d2,e7,f2,
g2,h1,a4,c1,
d3,e8,f3,g3,
h4,a1,c2,d4,
e1,f4,g4,h2,
a2,c4,d5,e2,
*/
        static void OnDuty()
        {
            List<List<string>> list = new List<List<string>>();
            List<string> listA = new List<string>(new string[] { "a1", "a2", "a3", "a4" });
            List<string> listB = new List<string>(new string[] { "b1", "b2", "b3" });
            List<string> listC = new List<string>(new string[] { "c1", "c2", "c3", "c4" });
            List<string> listD = new List<string>(new string[] { "d1", "d2", "d3", "d4", "d5" });
            List<string> listE = new List<string>(new string[] { "e1", "e2", "e3", "e4", "e5", "e6", "e7", "e8" });
            List<string> listF = new List<string>(new string[] { "f1", "f2", "f3", "f4" ,"f5"});
            List<string> listG = new List<string>(new string[] { "g1", "g2", "g3", "g4" ,"g5"});
            List<string> listH = new List<string>(new string[] { "h1", "h2", "h3" });
            list.Add(listA);
            list.Add(listB);
            list.Add(listC);
            list.Add(listD);
            list.Add(listE);
            list.Add(listF);
            list.Add(listG);
            list.Add(listH);
            int[] nextPos = new int[8];
            int dayCount = 9,startPos=0;
            startPos=GetData(list, nextPos, startPos, dayCount);
            Console.WriteLine();
            list[2].Remove("c3");//删除c3
            list[1].Remove("b1");//删除B处所有人员
            list[1].Remove("b2");
            list[1].Remove("b3");
            list[7].Insert(nextPos[7],"h4");//加入h4，并将其放到H处最后一个轮值的位置
              nextPos[7]++;//h4加入后，下一个轮值人员的下标应加1
            GetData(list, nextPos, startPos, dayCount);//继续排9天的班
        }        static int GetData(List<List<string>> list, int[] nextPos, int startPos, int dayCount)
        {
            int count = 0;
            while (count<dayCount)
            {
                for (int i = 0; i < 4; i++)
                {
                    if (list[(startPos + i) % 8].Count == 0)//发现某处没有轮值人员
                    {
                        startPos++;
                        i--;
                        continue;
                    }
                    Console.Write(list[(startPos + i) % 8][nextPos[(startPos + i) % 8]] + ",");
                    nextPos[(startPos + i) % 8] = (nextPos[(startPos + i) % 8] + 1) % list[(startPos + i) % 8].Count;
                }
                count++;
                startPos = (startPos + 4) % 8;
                Console.WriteLine();
            }
            return startPos;
        }

Answer 14

其实我觉得这个问题你把它分成两个层面来解决，就很简单了：一个是公司层面，一个是部门层面，比如说：class Company
{
　　List<Depart> departs = 部门列表;　　public Person[] GetWatchDepart()
　　{
　　　　Person[] watchPersons = new Person[4];
　　　　for(int i = 0; i != 4; ++i)
　　　　{
　　　　　　watchPersons[i] = departs[本次起始部门序号 + i].GetWatchPerson();
　　　　}
　　｝
}class Depart
{
　　List<Person> persons = 部门成员列表;
　　
　　public Person GetWatchDepart()
　　{
　　　　返回今天应该值日的人员
　　}
}这样的话，就变成处理一维数组的问题，简单多了，呵呵，不知道我的思路是不是符合楼主的要求。这样还有一个好处，就是如果具有一个部门的基类，那么就可以很简单的根据每个部门的具体要求来实现本部门内的排班规则。呵，家里没有 VS，只是把大致的思路写了出来，没有具体的去实现了。

Answer 15

谈谈我的思路：1. 同部门的人排序号，从1开始a1, a2, a3, a4
b1, b2, b3, b4, b5
c1, c2, c3, c4
d1, d2, d32. 每部门抽出序号最小的一个，同时，该人的序号重置为本部门 最大序号+1则 a1 --> a5
   b1 --> b6
   c1 --> c5
   d1 --> d43. 回到第二步说明：序号使用 32 位整型数，最大值 2147483647 （有符号），约 5883516 年
      使用数据库存储，写 SQL 代码比写其他的第三代高级语言代码简单。（呵呵，要不怎能叫做 4GL 呢）如是部门加了新人，则新人置序号 最大序号+1

Answer 16

不错, 这个也是我昨天晚上在写的,但是就是返回本处值班人难,并且,一周要返回多次,并且人还会不在,动态的,
我的难点就是解决动态数据这个问题了,现在还是没有个好的办法,
所以只好每周手工选择在位人员,更新各处人员队列,上周的轮到的各处最后一个人就只有记录到数据库里了
现在还要考虑公平问题,人少的处要轮的也一样多,则人少的处的人对我意见很大!!呵呵
1.怎么办?>????????
2.我再把节日值班的规则讲一下:类似该贴题目规则,节日增加了坐班(24小时坐着,呵呵),不过坐班简单,每天一个处确定一个人就行,不用实现这个了
要记录上次节日该处哪些人安排了值班和坐班,
这次节日轮到该处则尽量不安排那些人,
现实中现只有手工记录两套顺序,该处坐班人员顺序和该处节日值班人员顺序,所以导致某个节日某个人既值班又坐班,~痛苦
节日值班比平时工作日值班更辛苦,所以必须要考虑公平问题,
如果按照abcdefgh顺序轮换处,人少的处要轮的也一样多,则人少的处的就不能过节了!一个节日比如春节某个人甚至会值几次还有坐班!呵呵另外还有一些规则,搞不出来再拿来让大家讨论了

Answer 17

我看到这个最初的考虑也是用list，呵呵

Answer 18

先写一个，实现一部分，后面的要解决的问题已经很简单了public class Item
{
    public string Name = string.Empty;
    public Item Next = null;    public Item(string name)
    {
        this.Name = name;
        this.Next = null;
    }    public Item(string name, Item next)
    {
        this.Name = name;
        this.Next = next;
    }
}public class Link
{
    private Item Head = null;
    public string Name = string.Empty;    public void Remove(string name)
    {
        if (Head == null) return;        if (Head.Name == name) { Head = Head.Next; return; }        Item current = Head;        while (current != null)
        {
            if (current.Next.Name == name)
                current.Next = current.Next.Next;            current = current.Next;
        }
    }    public void Add(string name)
    {
        if (Head == null) { Head = new Item(name); return; }        Item current = Head;        while (current.Next != null) current = current.Next;        current.Next = new Item(name);
    }    public Item Get()
    {
        Item result = Head;        Head = Head.Next;        Add(result.Name);        return result;
    }    public void Debug()
    {
        Item current = Head;        while (current != null)
        {
            System.Diagnostics.Debug.Write(current.Name + "\t");            current = current.Next;
        }        System.Diagnostics.Debug.WriteLine(string.Empty);
    }
}public class Puzzle
{
    Link[] links = null;
    private string[][] _data = null;    public string[][] Data
    {
        get { return _data; }
        set { 
            _data = value; 
        }
    }    private void InitialLinks()
    {
        int i = default(int);        links = new Link[_data.GetLength(0)];        for (int j = 0; j < links.Length; j++) links[j] = new Link();        foreach (string[] ret in _data)
        {
            Link l = links[i++];            foreach (string r in ret) l.Add(r);
        }
    }    public string[][] GetSchedule(int count)
    {
        InitialLinks();        for (int i = 1; i <= count; i++)
        {
            if (i == 2)
            {
                links[0].Remove("a2");
            }
            else if (i == 4)
            {
                links[0].Add("a2");
            }            foreach (Link l in links)
            {
                l.Get();
                l.Debug();
            }
            System.Diagnostics.Debug.WriteLine(string.Empty);        }        return _data;   
    }
}
有空补上另一半

Answer 19

再补一部分（实现部门更换），PS：不好意思啊，要工作还要照顾一下股票，所以回帖比较慢，见谅
public class Item
{
    public string Name = string.Empty;  //名称
    public Item Next = null;            //下一个
    public int Count = default(int);    //值班次数
    public bool Tag = false;            //在某一轮是否已经值过班    public Item() { }    public Item(string name) : this()
    { this.Name = name; }    public Item(string name, Item next) :this(name)
    { this.Next = next; }
}public class Link
{
    public event EventHandler LoopEnded = null; //当全部成员执行结束以后触发    private Item Head = null;                   //第一个成员
    public string Name = string.Empty;          //部门名称
    public bool Tag = false;                    //某次部门循环结束    private bool CheckLoopEnded()   //某次检查循环是否结束
    {
        if (Head == null) return true;        Item current = Head;
        bool result = true;        while (result && current != null)
        {
            result &= current.Tag;
            current = current.Next;
        }        return result;
    }    private void ClearTags()
    {
        Item current = Head;        while (current != null)
        {
            current.Tag = false;
            current = current.Next;
        }
    }    public void Remove(string name) //某人请假
    {
        if (Head == null) return;        if (Head.Name == name) { Head = Head.Next; return; }        Item current = Head;        while (current.Next != null)
        {
            if (current.Next.Name == name)
                current.Next = current.Next.Next;            current = current.Next;
        }
    }    public void Add(string name)    //某人加入（请假回来）
    {
        Add(new Item(name));
    }    public void Add(Item item)      //某人加入（请假回来）
    {
        if (Head == null) { Head = item; return; }        Item current = Head;        while (current.Next != null) current = current.Next;        item.Next = null;
        current.Next = item;
    }    public void MoveNext()          //循环一轮
    {
        if (Head == null || Head.Next == null) return;        Item result = Head;        Head = Head.Next;        result.Count++;
        result.Tag = true;        Add(result);        if (CheckLoopEnded())
        {
            ClearTags();
            if (LoopEnded != null) LoopEnded(this, null);
        }
    }    public void Debug()
    {
        Item current = Head;        while (current != null)
        {
            System.Diagnostics.Debug.Write(string.Format("{0}[{1}]\t", current.Name, current.Count));            current = current.Next;
        }        System.Diagnostics.Debug.WriteLine(string.Empty);
    }
}public class Puzzle
{
    Link[] links = null;
    private string[][] _data = null;    public string[][] Data
    {
        get { return _data; }
        set { 
            _data = value; 
        }
    }    private void InitialLinks()
    {
        int i = default(int);        links = new Link[_data.GetLength(0)];        for (int j = 0; j < links.Length; j++)
        {
            links[j] = new Link();
            links[j].LoopEnded += new EventHandler(Puzzle_TurnEnd);
        }        foreach (string[] ret in _data)
        {
            Link l = links[i++];            foreach (string r in ret) l.Add(r);
        }
    }    private void Puzzle_TurnEnd(object sender, EventArgs e)
    {
        Link l = (sender as Link);        l.Tag = true;
    }    public string[][] GetSchedule(int count, int department_count)
    {
        InitialLinks();        int k = 0;        for (int i = 1; i <= count; i++)
        {
            if (i == 2)
            {
                links[0].Remove("d2");//d2在第二天请假
            }
            else if (i == 4)
            {
                links[0].Add("d2");//d2在第4天请假回来
            }            bool result = true;            for (int j = k; j < k + department_count; j++)
            {
                if (j >= links.Length) break;                Link l = links[j];                l.MoveNext();
                l.Debug();                result &= l.Tag;
            }            if (result)
            {
                System.Diagnostics.Debug.WriteLine("Turn End");
                for (int j = k; j < k + department_count; j++)
                {
                    if (j >= links.Length) break;                    links[j].Tag = false;
                }                if (k + department_count >= links.Length) k = 0;
                else k += department_count;
                
            }            System.Diagnostics.Debug.WriteLine(string.Empty);        }        return _data;   
    }
}

Answer 20

受不了了，有那么难吗？有5000分的人，自己搞不ding?