1

我刚刚开始从事一个涉及一些调度优化的项目，我担心自己陷入了数学困境。我想知道您是否可以想到任何巧妙的方法来执行以下操作。

这是基础知识：

  • 您有 x 个时隙
  • 你有 y 名教师面试官
  • 你有z个面试的申请人
  • x 和 y 不必相等（可以有不同数量的采访者和被采访者）
  • 一个时间段可能没有人被采访。
  • 这些组成了一个表格作为时间表，其中行标题是面试官（用数字表示），列标题是时间段（用数字表示），单元格本身是正在面试的申请人。

约束：

  • z 数字只能像数独一样在每行/列中出现一次（因为申请人不能与同一个面试官面试两次，他/她也不能一次面试两次）。
  • 整个表格中每个 z 数字必须恰好有 3 个（因为所有申请人都必须恰好面试 3 次）。

最终，将使用一些公式来计算每个有效配置的加权分数，以确定板的“最佳”状态。为了解释起见，我们只会说它类似于 2a + 5b，其中 a 和 b 是面试官与申请人共同拥有的不同类型的品质，但这目前并不重要。

我试图想出某种方法来生成所有可能的有效配置并最终计算每个有效配置的分数，最后选择得分最高的那个。我在寻找一种聪明的方法时遇到了一些问题。

最初，我觉得自己并不聪明，并考虑过暴力破解它，但这基本上是不可能的，因为可能性很大。

你能想出什么更聪明的方法来修剪一些错误的配置，或者一个聪明的方法来生成有效的板来进行加权分数检查吗？

4

2 回答 2

1

这是 MiniZinc 中一个非常简单的约束编程模型 - 给定适当的求解器 - 为（我的解释）问题生成所有可能的有效解决方案。然而，正如@TimChippingtonDerrick 指出的那样，对于更复杂的问题实例，解决方案太多了。

也就是说，如果可以在模型中以某种方式说明目标（obj = "2a + 5b"）（例如，使用面试官/申请人的一些额外数据等），只需将其更改为优化问题，即最小化或最大化该目标。

因此，这里是一个简单问题实例（x=10、y=5、z=10 和 m=3）的 MiniZinc 模型。注：在面试表中，数值0（零）表示当时没有面试官的面试。

include "globals.mzn"; 

int: x = 10; % number of time slots
int: y =  5; % number of faculty interviewers
int: z = 10; % number of applicants interviewing

int: m = 3; % number of times each applicants will be interviewed

% decision variables
% The interview table:
%   1..y: rows (interviewers)
%   1..x: columns (time slots)
array[1..y, 1..x] of var 0..z: s;

% solve satisfy;
solve :: int_search([s[i,j] | i in 1..y, j in 1..x], first_fail, indomain_random, complete) satisfy;

constraint

    % A z digit can only appear once in each row/column like Sudoku (because an applicant 
    % can't interview with the same interviewer twice and he/she can't interview twice at once).
    forall(a in 1..z) (
       % rows
       forall(i in 1..y) (
          %sum([bool2int(s[i,j] = a) | j in 1..x]) <= 1
          alldifferent_except_0([bool2int(s[i,j] = a) | j in 1..x])
       )
       /\
       % columns
       forall(j in 1..x) (
          % sum([bool2int(s[i,j] = a) | i in 1..y]) <= 1
          alldifferent_except_0([bool2int(s[i,j] = a) | i in 1..y])
       )
    )

    % There has to be exactly 3 of each z number in the entire table 
    % (because all applicants have to interview exactly 3 times).
    /\
    forall(a in 1..z) (
       count([s[i,j] | i in 1..y, j in 1..x], a, m)
    )
;

% constraint
%   % symmetry breaking: assign applicant a to interviewer a in time a (if possible)
%   forall(a in 1..z where a <= y) (
%      s[a,a] = a
%   )
% ;


output [
   "x (number of time slots (rows): " ++ show(x) ++ "\n" ++
   "y (number of interviews (columns): " ++ show(y) ++ "\n" ++
   "z (number of applicants): " ++ show(z) ++ "\n"
]
++
[
  if j = 1 then "\n" else " " endif ++
    show_int(2,s[i,j])
  | i in 1..y, j in 1..x
];

对于这个问题（x=10，y=5，z=10），有大量的解决方案。这是其中的两个：

x (number of time slots (rows): 10
y (number of interviews (columns): 5
z (number of applicants): 10

5  2 10  8  0  6  7  4  3  9
3  1  5  7  0  2  9  6  8  4
8  0  0  5  6  1 10  3  0  7
2 10  1  0  0  9  0  0  0  0
0  0  0  0  0  4  0  0  0  0
----------
x (number of time slots (rows): 10
y (number of interviews (columns): 5
z (number of applicants): 10

 5  2 10  8  0  6  7  4  3  9
 3  1  5  7  0  2  9  6  8  4
 8  0  0  5  6  1 10  3  0  7
 2 10  0  1  0  9  0  0  0  0
 0  0  0  0  0  4  0  0  0  0

（这个 MiniZinc 模型也在这里：http ://www.hakank.org/minizinc/interview_scheduling.mzn ）

对一个更简单的问题 (x=6,y=3,z=3, m=3) 的数字注释以显示问题的多样性：不使用对称破坏时有 317760 种不同的解决方案（在代码）。随着对称性的破坏，它的解决方案要少得多：1300。这是这些解决方案之一：

1  0  0  3  2  0
3  2  1  0  0  0
0  1  3  2  0  0
于 2013-10-26T08:39:52.347 回答
0

它在上面的回复中没有说明，可能是因为它对我们中的一些人来说是显而易见的，但是仅仅试图列举所有的合法组合只会在这类问题的非常小的测试用例中起作用。如果您尝试幼稚的实现，您将很快在计算时间上碰壁。

正如其他人所建议的那样，如果您想针对实际规模的问题执行此操作，则需要考虑使用一些优化工具。免费解算器之一，如 COIN-OR、glpk 或 lpsolve；或其中一种商业工具-它们可能会变得昂贵，但是如果您有足够大的问题，那么它们很容易物有所值。

于 2013-10-24T13:32:54.997 回答