Initializing help system before first use

Assigning workers to machines: heuristics and user-defined search


Type: Assignment
Rating: 2
Description: Assigning workers to machines: linear, 'all-different', and 'element' constraints;
  • branching strategy for variables; consecutive solving with 2 different objectives; heuristic solution algorithm without enumeration (i1assign_ka.mos).
  • User-defined search: definition of variable and value selection strategies (i1assign2_ka.mos).
File(s): i1assign_ka.mos, i1assign2_ka.mos
Data file(s): i1assign.dat


i1assign_ka.mos
(!******************************************************
   CP Example Problems
   ===================

   file i1assign_ka.mos
   ````````````````````
   Assigning workers to machines
   (See "Applications of optimization with Xpress-MP",
        Section 14.1 Assigning personnel to machines)
   - Exact and heuristic solutions -
   
   (c) 2008 Artelys S.A. and Fair Isaac Corporation
       
*******************************************************!)

model "I-1 Personnel assignment (CP)"
 uses "kalis"

 forward procedure parallel_heur
 forward procedure print_sol(text1,text2:string, objval:integer)

 declarations
  PERS = 1..6                        ! Personnel
  MACH = 1..6                        ! Machines
  OUTP: array(PERS,MACH) of integer  ! Productivity
 end-declarations

 initializations from 'Data/i1assign.dat'
  OUTP
 end-initializations
 
! **** Exact solution for parallel machines ****

 declarations
  assign: array(PERS) of cpvar       ! Machine assigned to a person 
  output: array(PERS) of cpvar       ! Productivity of every person
  totalProd: cpvar                   ! Total productivity
  O: array(MACH) of integer          ! Auxiliary array for constraint def.
  Strategy: cpbranching              ! Branching strategy
 end-declarations

 forall(p in PERS) setdomain(assign(p), MACH)

! Calculate productivity per worker
 forall(p in PERS) do
  forall(m in MACH) O(m):= OUTP(p,m)
  element(O, assign(p)) = output(p)
 end-do
 
! Calculate total productivity
 totalProd = sum(p in PERS) output(p)

! One person per machine
 all_different(assign)

! Branching strategy
 Strategy:= assign_var(KALIS_LARGEST_MAX, KALIS_MAX_TO_MIN, output)
 cp_set_branching(Strategy)

! Solve the problem
 if cp_maximize(totalProd) then
  print_sol("Exact solution (parallel assignment)", "Total", getsol(totalProd))
 end-if

! **** Exact solution for serial machines ****

 declarations
  pmin: cpvar                        ! Minimum productivity
 end-declarations

! Calculate minimum productivity
 pmin = minimum(output)

! Branching strategy
 Strategy:= assign_var(KALIS_SMALLEST_MIN, KALIS_MAX_TO_MIN, output)
 cp_set_branching(Strategy)

! Solve the problem
 if cp_maximize(pmin) then
  print_sol("Exact solution (serial machines)", "Minimum", getsol(pmin))
 end-if

! **** Heuristic solution for parallel machines ****
 parallel_heur

!-----------------------------------------------------------------

! Heuristic solution for parallel assignment
 procedure parallel_heur
  declarations
   ALLP, ALLM: set of integer        ! Copies of sets PERS and MACH
   HProd: integer                    ! Total productivity value
   pmax,omax,mmax: integer
  end-declarations

 ! Copy the sets of workers and machines
  forall(p in PERS) ALLP+={p}
  forall(m in MACH) ALLM+={m}

 ! Assign workers to machines as long as there are unassigned persons
  while (ALLP<>{}) do
   pmax:=0; mmax:=0; omax:=0

 ! Find the highest productivity among the remaining workers and machines
   forall(p in ALLP, m in ALLM)
    if OUTP(p,m) > omax then
     omax:=OUTP(p,m)
     pmax:=p; mmax:=m
    end-if

   assign(pmax) = mmax               ! Assign chosen machine to person pmax
   ALLP-={pmax}; ALLM-={mmax}        ! Remove person and machine from sets
  end-do

  writeln("Heuristic solution (parallel assignment):")
  forall(p in PERS)
   writeln("  ",p, " operates machine ", getval(assign(p)),
           " (",getval(output(p)), ")")
  writeln("  Total productivity: ", getval(totalProd))
 end-procedure

!-----------------------------------------------------------------

! Solution printing
 procedure print_sol(text1,text2:string, objval:integer)
  writeln(text1,":")
  forall(p in PERS)
   writeln("  ",p, " operates machine ", getsol(assign(p)),
           " (",getsol(output(p)), ")")
  writeln("  ", text2, " productivity: ", objval)
 end-procedure
 
end-model

i1assign2_ka.mos
(!******************************************************
   CP Example Problems
   ===================

   file i1assign2_ka.mos
   `````````````````````
   Assigning workers to machines
   (See "Applications of optimization with Xpress-MP",
        Section 14.1 Assigning personnel to machines)
   - User-defined search strategies -
   
   (c) 2008 Artelys S.A. and Fair Isaac Corporation
       Creation: 2005, rev. Mar. 2013       
*******************************************************!)

model "I-1 Personnel assignment (CP)"
 uses "kalis"

 forward function varchoice(Vars: cpvarlist): integer
 forward function varchoicemin(Vars: cpvarlist): integer
 forward function valchoice(x: cpvar): integer
 forward procedure print_sol(text1,text2:string, objval:integer)

 declarations
  PERS = 1..6                        ! Personnel
  MACH = 1..6                        ! Machines
  OUTP: array(PERS,MACH) of integer  ! Productivity
 end-declarations

 initializations from 'Data/i1assign.dat'
  OUTP
 end-initializations
 
! **** Exact solution for parallel assignment ****

 declarations
  assign: array(PERS) of cpvar       ! Machine assigned to a person 
  output: array(PERS) of cpvar       ! Productivity of every person
  totalProd: cpvar                   ! Total productivity
  O: array(MACH) of integer          ! Auxiliary array for constraint def.
  Strategy: cpbranching              ! Branching strategy
 end-declarations

 forall(p in PERS) setdomain(assign(p), MACH)

! Calculate productivity per worker
 forall(p in PERS) do
  forall(m in MACH) O(m):= OUTP(p,m)
  element(O, assign(p)) = output(p)
 end-do
 
! Calculate total productivity
 totalProd = sum(p in PERS) output(p)

! One person per machine
 all_different(assign)

! Branching strategy
 Strategy:= assign_var("varchoice", "valchoice", output)

! Solve the problem
 if cp_maximize(totalProd) then
  print_sol("Exact solution (parallel assignment)", "Total", getsol(totalProd))
 end-if

! **** Exact solution for serial machines ****

 declarations
  pmin: cpvar                        ! Minimum productivity
 end-declarations

! Calculate minimum productivity
 pmin = minimum(output)

! Branching strategy
 Strategy:= assign_var("varchoicemin", "valchoice", output)

! Solve the problem
 if cp_maximize(pmin) then
  print_sol("Exact solution (serial machines)", "Minimum", getsol(pmin))
 end-if
 
!-----------------------------------------------------------------
! **** Variable choice: choose the variable(s) with largest domain value and
!      among these the one with the smallest next-best value
 function varchoice(Vars: cpvarlist): integer
  declarations
   Vset,Iset: set of integer
  end-declarations

 ! Set of uninstantiated variables
  forall(i in 1..getsize(Vars))
   if not is_fixed(getvar(Vars,i)) then Vset+= {i}; end-if
 
  if Vset={} then
   returned:= 0
  else 
  ! Get the variable(s) with largest upper bound
   dmax:= max(i in Vset) getub(getvar(Vars,i)) 
   forall(i in Vset)
    if getub(getvar(Vars,i)) = dmax then Iset+= {i}; end-if
   dmin:= dmax

  ! Choose variable with smallest next-best value among those indexed by 'Iset'
   forall(i in Iset) do
    prev:= getprev(getvar(Vars,i),dmax)
    if prev < dmin then
     returned:= i
     dmin:= prev
    end-if 
   end-do
  end-if 
 end-function

! **** Variable choice: choose the variable(s) with smallest domain value and
!      among these the one with the smallest upper bound
 function varchoicemin(Vars: cpvarlist): integer
  declarations
   Vset,Iset: set of integer
  end-declarations

 ! Set of uninstantiated variables
  forall(i in 1..getsize(Vars))
   if not is_fixed(getvar(Vars,i)) then Vset+= {i}; end-if
 
  if Vset={} then
   returned:= 0
  else 
  ! Get the variable(s) with smallest lower bound
   dmin:= min(i in Vset) getlb(getvar(Vars,i)) 
   forall(i in Vset)
    if getlb(getvar(Vars,i)) = dmin then Iset+= {i}; end-if

  ! Choose variable with smallest upper bound among those indexed by 'Iset'
   dmax:= getparam("kalis_default_ub")
   forall(i in Iset)
    if getub(getvar(Vars,i)) < dmax then
     returned:= i
     dmax:= getub(getvar(Vars,i))
    end-if 
  end-if 
 end-function

! **** Value choice: choose the largest value in the variable's domain 
 function valchoice(x: cpvar): integer
  returned:= getub(x)
 end-function
 
!-----------------------------------------------------------------

! Solution printing
 procedure print_sol(text1,text2:string, objval:integer)
  writeln(text1,":")
  forall(p in PERS)
   writeln("  ",p, " operates machine ", getsol(assign(p)),
           " (",getsol(output(p)), ")")
  writeln("  ", text2, " productivity: ", objval)
 end-procedure
 
end-model