在给定一系列可能任务的情况下，如何优化工人的劳动时间以最大程度地利用时间 [英] How to optimize makespan of worker labor to maximum time usage given a set of possible tasks
问题描述
所以我在算法建模方面有点困难，希望你们能帮助我找到一些方向.问题出在我公司的物流部门，作为一名CS实习生，我现在还找不到解决方案
So I'm in a bit of a difficult algorithm modeling situation and I hope you guys can help me find some directions. The problem came of logistics department of my company, and as a CS intern, I wasn't able to find a solution yet
问题:在给定的时间量，固定数量的工作人员和一组可行的任务下，以使所有工作人员都尽可能忙碌的方式向工作人员分配任务，并且该组的最后一个工作人员仅被分配给其他人无法承担的其余任务.
The problem: Given a fixed amount of time, a fixed number of workers and a set of feaseble tasks, assign tasks to workers in such a way that all workers be as busy as possible, and the last worker of the group is only assigned to the remaining tasks that others weren't able to bear.
此方法的目的是使最后一个工作人员尽可能地自由，以便他只能在真正需要的时候从事这些工作
约束:
- 到期时间:每个任务都有自己的到期时间.这意味着任务可以在任何时候都可以开始，只要它按时完成就可以了.
- 没有重叠:一个工人不能完成多个任务，并且一个任务不能在多个工人之间划分
到目前为止，我已经尝试过...
So far I've tried...
- Job-Shop问题:情况似乎并非如此，因为不能将任务分组为作业，而这些作业必须由特定机器(在我们的情况下为工人)进行处理.在我的情况下，任务可以由任何工作人员完成，而无需任何偏好.
- 灵活的JSP:我真的以为是我的情况，因为任务可以由任何机器(工人)处理.但是我无法弄清楚如何将我的任务按工作分组，因为它们没有明确的顺序，而只是按时.
我也尝试了通过Google OR-Tools的方法，但是似乎都没有解决这个问题的方法.看起来像是NP完全问题，尽管任务和工作人员的规模并不大，但我认为蛮力组合任务以寻找解决方案并不是一种方法.
I've tried approaches via google OR-Tools too, but none seemed fit to the problem. As it looks like a NP-complete problem, I don't think bruteforce combining tasks in order to find a solution is a way, although the set of tasks and workers is not that large.
这里有一些我读过的文章，以找到类似的解决方案:
Here are some articles I've read in order to find a similar solution:
提前谢谢！
推荐答案
同构问题已解决.我假设每个任务都是必需的工作，并且工作人员是可以互换的:例如，保罗将能够在与艾比完全相同的时间内完成任务17.
Isomorphic problems have been solved. I assume that each task has a required effort, and that workers are interchangeable: for instance, Paul will be able to finish task #17 in exactly the same amount of time as Abby.
由此，调度变得很简单:为每个任务计算一个最新开始时间"(LST)，最后期限减去所需的工作量.例如，一项耗时4小时且在18:00到期的任务的LST为14:00.
With this, scheduling turns out to be trivial: compute a "latest start time" (LST) for each task, the deadline minus the effort required. For instance, a task that takes 4 hours and is due at 18:00, has a LST of 14:00.
呼叫可用工作人员的数量N+1，其中+1是按需工作人员.
call the number of available workers N+1, where the +1 is the on-demand worker.
按LST对任务进行排序，然后按顺序将其分配给N可用的工作程序.按明显的时间间隔填写时间表:每位工作人员完成当前任务后，分配下一个可用任务.
Sort the tasks by LST, and assign them to the N available workers in that order. Fill out the schedule with the obvious intervals: as each worker finishes the current task, assign the next available task.
如果到达时间表中某个LST而没有指定工作人员的时间点，则将其放入按需工作人员N+1的队列中.到最后，如果工人N+1的任务多于可用时间，那么您就没有解决方案.
If you reach a point in the schedule where you have a LST without an assigned worker, put that into the queue for the on-demand worker, N+1. When you get to the end, if worker N+1 has more tasks than time available, then you have no solution.
例如，给定2 + 1个工作人员和任务
For instance, given 2+1 workers and tasks
Due Effort LST (computed from input)
A 5 3 2
B 3 2 1
C 1 1 0
D 5 2 3
E 4 3 1
按LST对列表进行排序
Sort the list by LST
Due Effort LST
C 1 1 0
E 4 3 1
B 3 2 1
A 5 3 2
D 5 2 3
我们现在开始按小时列出每个工人的时间表
We now begin to lay out the schedule for each worker by hour
0 1 2 3 4
#1 C B B
#2 E E E
这时，我们看到必须启动任务A，但是两个正常的工作人员已经很忙.我们必须将 something 分配给#3.作业跨度的过载为1小时(实际上，这是整个计划的过载)，因此将1个小时的作业交换为#3，并在其LST处启动过载"作业(这将减少回溯并重新执行在复杂的情况下尝试).
At this point, we see that task A must be started, but the two normal workers are already busy. We have to assign something to #3. The overload for the job span is 1 hour (indeed, that's the entire schedule overload), so swap the 1-hour job to #3 and start the "overload" job at its LST (this will reduce the amount of backtracking and re-tries in a complex situation).
0 1 2 3 4
#1 B B A A A
#2 E E E
#3 C
现在，任务D很容易分配给#2，我们已经完成.
Now, task D is easily assigned to #2, and we're done.
这会让你动起来吗?
这篇关于在给定一系列可能任务的情况下，如何优化工人的劳动时间以最大程度地利用时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
