1
$\begingroup$

This is an online assignment problem and yet can be considered as an assignment problem with a sequence. Assume that workers are coming into the system sequentially and I want to assign a task to them based on their cost for each task. I have set up the python model without the sequence constraint, I just couldn't figure out how to mandate the order: This example from the OR-Tools: In the example there are four workers (numbered 0-3) and four tasks (numbered 0-3).

The costs of assigning workers to tasks are shown in the following table.

0 1 2 3
0 90 80 75 70
1 35 85 55 65
2 125 95 90 85
3 45 110 95 115

The problem is to assign each worker to at most one task, with no two workers performing the same task while minimizing the total cost. Since there are more workers than tasks, one worker will not be assigned a task.

Assume that I want to force an order/ sequence. Say worker 0 has to be assigned first worker 2, then worker 3... So in practice:

  • worker 0 assigned to task 3 (lowest cost)
  • worker 1 assigned to task 0 (lowest cost)
  • worker 2 assigned to task 2 (task 3 has the lowest cost but since it is already assigned to worker 0 it is not available)
  • worker 3 assigned to task 1

MIP solution The following sections describe how to solve the problem using the MIP solver as an assignment problem without enforcing the order.

Import the libraries The following code imports the required libraries.

from ortools.linear_solver import pywraplp

The following code declares the MIP solver.

# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver('SCIP')

The following code creates the data for the problem.

costs = [
[90, 80, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 85],
[45, 110, 95, 115],
]
num_workers = len(costs)
num_tasks = len(costs[0])

The following code creates binary integer variables for the problem.

# x[i, j] is an array of 0-1 variables, which will be 1
# if worker i is assigned to task j.
x = {}
for i in range(num_workers):
   for j in range(num_tasks):
      x[i, j] = solver.IntVar(0, 1, '')

The following code creates the constraints for the problem.

# Each worker is assigned to at most 1 task.
for i in range(num_workers):
solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) <= 1)

# Each task is assigned to exactly one worker.
for j in range(num_tasks):
solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) == 1)

HERE I want to add another constraint(s) that forces the order

The following code creates the objective function for the problem.

objective_terms = []
for i in range(num_workers):
   for j in range(num_tasks):
       objective_terms.append(costs[i][j] * x[i, j])
solver.Minimize(solver.Sum(objective_terms))

The value of the objective function is the total cost over all variables that are assigned the value 1 by the solver.

Invoke the solver The following code invokes the solver and prints the solution.

status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
print('Total cost = ', solver.Objective().Value(), '\n')
for i in range(num_workers):
    for j in range(num_tasks):
        # Test if x[i,j] is 1 (with tolerance for floating point arithmetic).
        if x[i, j].solution_value() > 0.5:
            print('Worker %d assigned to task %d.  Cost = %d' %
                  (i, j, costs[i][j]))
$\endgroup$
1
  • $\begingroup$ You posted data for 4 tasks and 4 resources whereas you mentioned workers are more than tasks, could you please explain and also what constraint you want to include ? Is it just that 1Task per worker or other constraints are there too ? And is objective that you want to minimize total cost of Tasks wrt workers they are assigned to (That's what I made out from explanation). And also what are problems you facing as you've included almost all the program so aren't you getting desired OP ? $\endgroup$ Sep 1, 2021 at 7:36

0

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.