There are $N$ workers and $2N$ jobs, named from $J_1$ to $J_{2N}$. There's a matrix $M$ denoting the subset of jobs can be handled by each worker: If $M_{i, j}$ is true, then worker $i$ can do job $j$.

Our task is to assign exact 2 jobs for each worker, s.t., each job is handled by exact one worker with respect to $M$. (So far the problem can be solved with max flow.) Moreover, If a worker $i$ handles job $j$, it can't handle job $j+1$.

The problem asks:

  1. If there exists such an assignment
  2. If there is, find out a solution to $\max_{Assignment}{\min_{i} {\left| J1_i - J2_i \right|}}$, where $J1_i$ is the first job assigned to worker $i$, and $J2_i$ is the second job assigned to worker $i$. In other words, to maximize the minimum interval between two jobs for all workers.
  • $\begingroup$ By the way I'm not sure if the tag fits the question well. Feel free to help me update it if possible $\endgroup$ – lz96 Oct 17 '19 at 6:34
  • $\begingroup$ what have you tried? $\endgroup$ – Yamar69 Oct 17 '19 at 7:06
  • $\begingroup$ @yamar69 I tried to model it as a cost flow problem but it doesn't work. For 2) we can probably binary search the upper bound and verify w/ algorithms similar in 1). Generally I have no working idea. $\endgroup$ – lz96 Oct 17 '19 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.