生成时间表 - 需要好的算法

昨天在试图入睡时，我开始考虑如何解决下面的问题，并意识到我无法想出一个好的算法。即使它看起来像一个，这不是一个学校作业，我只想找到答案。 :)生成时间表 - 需要好的算法

基本上让我们设想一个工作时间表，在一家商店的员工。该计划应根据一系列要求生成计划建议。

的要求是：

只有一个员工任何一周的工作。
员工无法连续工作两周。
应该有防止雇员从得到安排某一周（假期）的工作方式。
分配应该尽可能平均，即如果我们有员工A，B和C，他们应该获得大约相同的周数，并且这些周应该尽可能均匀地分配为。

什么是攻击这个问题的最好方法是什么？也许函数式编程更适合解决这个问题？

编辑：现在我知道这种类型的问题被称为“资源约束调度”。由于“调度”常常涉及计划任务或线程等事情，所以对于这一点有点困难。对于谁仍然认为我所要求的作业方案（尽管我明确地声称，否则以上）的人，你可以看看我以前的问题，我想他们清楚地表明我不是一个学生......

来源

2011-08-29 rickythefox

贪婪：使用一个PriorityQueue应该是一个很好的启发式方法，但如果某个员工在最后一个预定的几周内有一个长期“奉献”，可能会失败。 – amit

什么是假期限制？ – naveen

尝试将输入参数和输出值添加到问题中的算法，因为这会使其更清晰 – Ankur

即使它好像这是家庭作业，我更愿意相信你。

这里是我想出来的：

let rec assignWork n upTo last workers = 
    if n <= upTo then 
     let checkNameIsEqualToLast = 
      match last with 
      | Some n -> ((=) n) 
      | _ -> fun _ -> false 
     let (name, _, _) as worker = 
      workers 
      |> List.filter (not << fun (name, _, v) -> checkNameIsEqualToLast name || List.exists ((=) n) v) 
      |> List.sortBy (fun (_, w, _) -> w) 
      |> List.head 
     workers 
     |> List.map (function 
      | n, w, v when n = name -> n, w + 1, v 
      | w -> w) 
     |> assignWork (n + 1) upTo (Some name) 
     |> fun t -> name::t 
    else []

例如：

let workers = 
    List.zip 
     [ 'A' .. 'E' ] 
     [ 
      [] 
      [ 2 .. 4 ] 
      [ 3 .. 5 ] 
      [ 1 .. 10000 ] 
      [ 3 ] 
     ] 
    |> List.map (fun (c, v) -> c, 0, v) 

assignWork 1 16 None workers

输出（似乎是合理的我）：

val it : char list = 
    ['A'; 'C'; 'A'; 'E'; 'B'; 'C'; 'B'; 'E'; 'A'; 'B'; 'C'; 'E'; 'A'; 'B'; 'C'; 'E']

来源

2011-08-29 08:34:38

感谢您的代码示例。至于这是作业，你可以检查我的网站上的其他问题，看到我明显失学了...... :) – rickythefox

你的结果会让B连续工作两次。根据这个问题，这是被禁止的，对吗？ – primfaktor

我的不好，修好了。 –

第一两点是对这个问题的限制。第三点指示排序候选解决方案的方法，如果将其正式化，则会出现优化问题。事实上，你正试图最小化工作分配上的差异。

请注意，由于受到限制，问题可能没有可接受的解决方案。

这是一个组合优化问题，您可以使用整数线性规划方法或大致随机随机局部搜索方法（它们也称为元启发式或许多其他名称）来解决它，例如遗传算法，模拟退火，禁忌搜索，迭代局部搜索，蚁群优化等。

这个特定类的问题被称为作业调度和有很多关于它的文献有许多变种。

如果这不是一项功课，我认为这应该足以满足你的好奇心，如果是这样的话，我想我告诉过你可以看看。

来源

2011-08-29 08:17:06 Teudimundo

生成时间表 - 需要好的算法

回答

相关问题