如何在有限制条件下解决作业分配问题？

Question

假设有N个人和M个任务，还有一个成本矩阵，告诉我们当将一项任务分配给一个人时，它的成本是多少。

假设我们可以将多个任务分配给同一个人。这意味着如果将所有任务分配给一个人可以使成本最小，则可以这样做。我知道这个问题可以使用各种技术来解决。其中一些如下所示：

- 位掩码 - 匈牙利算法 - 最小成本最大流 - 蛮力法（所有排列M！）

问题：但是如果我们加上一个限制条件，例如只能将连续任务分配给一个人呢？

    T1   T2   T3
P1   2    2    2
P2   3    1    4

答案是6而不是5。

解释：

我们可能会认为，P1->T1，P2->T2，P1->T3 = 2+1+2 = 5 可以是答案，但事实并非如此，因为(T1和T3是连续的，所以不能分配给P1)。

P1->T1, P1->T2, P1-T3 = 2+2+2 = 6

如何解决这个问题？

- chindirala sampath kumar

---

当有更多的人和任务时，逻辑是否容易编码？ - chindirala sampath kumar

https://stackoverflow.com/a/62593556/2034787 - גלעד ברקן

@user3386109 我认为你是不对的。没有限制条件，你可以将每个工作分配给最低成本的人。有了限制条件，到了列表的一半，你会遇到一个特定的人，已经用完了一组人，每一步都要考虑是否切换到剩余的人。尝试将100个任务分配给30个人，你的中间数据结构中有数十亿个选项。 - btilly

@btilly 是的，我在问题中被几件事情分散了注意力，并没有意识到问题（没有约束条件）真正的本质：只需为每个任务选择最小值。 - user3386109

Answer 1

您可以使用整数线性规划（ILP）来解决此问题。

以下是类似OPL的伪代码：

**input: 
two integers N, M        // N persons, M tasks
a cost matrix C[N][M] 

**decision variables: 
X[N][M][M]     // An array with values in {0, 1}
               // X[i][j][k] = 1 <=> the person i performs the tasks j to k 
                              

**constraints:
// one person can perform at most 1 sequence of consecutive tasks
for all i in {1, N}, sum(j in {1, ..., M}, k in {1, ..., M}) X[i][j][k] <= 1

// each task is performed exactly once
for all t in {1, M}, sum(i in {1, ..., N}, j in {1, ..., t}, k in {t, ..., M}) X[i][j][k] = 1

// impossible tasks sequences are discarded
for all i in {1, ..., N}, for all j in {1, ..., M}, sum(k in {1, ..., j-1}) X[i][j][k] = 0

**objective function:
minimize sum(i, j, k) X[i][j][k] * (sum(t in {j, ..., k}) C[t])

我认为在这里，ILP可能是最好的工具，因为通常使用它来解决调度和生产计划问题。
如果您没有编写LP程序的经验，不用担心，它比看起来要容易得多，而且这个问题相当容易和适合入门。

还有一个专门解决此类问题和解决方案的stackexchange，即OR stack exchange。

- m.raynal

Answer 2

对我来说，这看起来是np完全问题。如果我没错的话，就不会有一个普遍快速的解决方案，最好的方法是使用最佳启发式方法来解决这个问题。

你没有提到的一种方法是使用A*搜索进行构造性方法。在这种情况下，搜索将沿着矩阵从左向右移动，并在每一步添加候选项到优先队列中。队列中的每个项都由当前列索引、迄今为止花费的总成本和已经行动过的人员列表组成。任何给定状态的剩余成本启发式是所有剩余列的列最小值之和。

我确定这可以找到一个解决方案，只是我不确定这是否是最佳方法。一些快速的谷歌搜索显示A*已经应用于几种类型的调度问题。

编辑：这里是实现。

public class OrderedTasks {

private class State {
    private final State prev;
    private final int position;
    private final int costSoFar;
    private final int lastActed;
    
    public State(int position, int costSoFar, int lastActed, State prev) {
        super();
        this.prev = prev;
        this.lastActed = lastActed;
        this.position = position;
        this.costSoFar = costSoFar;
    }

    public void getNextSteps(int[] task, Consumer<State> consumer) {
        Set<Integer> actedSoFar = new HashSet<>();
        State prev = this.prev;
        if (prev != null) {
            for (; prev!=null; prev=prev.prev) {
                actedSoFar.add(prev.lastActed);
            }
        }
        for (int person=0; person<task.length; ++person) {
            if (actedSoFar.contains(person) && this.lastActed!=person) {
                continue;
            }
            consumer.accept(new State(position+1,task[person]+this.costSoFar,
                    person, this));
        }
    }
}

public int minCost(int[][] tasksByPeople) {
    int[] cumulativeMinCost = getCumulativeMinCostPerTask(tasksByPeople);
    Function<State, Integer> totalCost = state->state.costSoFar+(state.position<cumulativeMinCost.length? cumulativeMinCost[state.position]: 0);
    PriorityQueue<State> pq = new PriorityQueue<>((s1,s2)->{
        return Integer.compare(totalCost.apply(s1), totalCost.apply(s2));
    });
    State state = new State(0, 0, -1, null);
    for (; state.position<tasksByPeople.length; state = pq.poll()) {
        state.getNextSteps(tasksByPeople[state.position], pq::add);
    }
    return state.costSoFar;
}

private int[] getCumulativeMinCostPerTask(int[][] tasksByPeople) {
    int[] result = new int[tasksByPeople.length];
    int cumulative = 0;
    for (int i=tasksByPeople.length-1; i>=0; --i) {
        cumulative += minimum(tasksByPeople[i]);
        result[i] = cumulative;
    }
    return result;
}

private int minimum(int[] arr) {
    if (arr.length==0) {
        throw new RuntimeException("Not valid for empty arrays.");
    }
    int min = arr[0];
    for (int i=1; i<arr.length; ++i) {
        min = Math.min(min, arr[i]);
    }
    return min;
}

public static void main(String[] args) {
    OrderedTasks ot = new OrderedTasks();
    System.out.println(ot.minCost(new int[][]{{2, 3},{2,1},{2,4},{2,2}}));
}
}

- John Angland

Answer 3

我认为你的问题非常类似于： 查找最小值

如果工人数量很大，这可能不是最佳方法，但易于理解和实现的方法可能是：

1. 获取所有可能重复使用工人W的组合列表，例如使用https://www.geeksforgeeks.org/combinations-with-repetitions/中的算法。这将给出像[[W1,W3,W2,W3,W1],[W3,W5,W5,W4,W5]之类的东西
2. 丢弃工人不连续的组合

bool isValid=true;
for (int kk = 0; kk < workerOrder.Length; kk++)
    {    
        int state=0;
        for (int mm = 0; mm < workerOrder.Length; mm++)
        {
            if (workerOrder[mm] == kk && state == 0) { state = 1; } //it has appeard
            if (workerOrder[mm] != kk && state == 1 ) { state = 2; } //it is not contious
            if (workerOrder[mm] == kk && state == 2) { isValid = false; break; } //it appeard again
        }
        if (isValid==false){break;}
    }

使用经过筛选的列表来使用表格检查时间，并保留最小值。

- SandiaDeDia