I'm trying to implement a Shift Scheduling system based on Nurse Rostering example. Unfortunately, i cannot get it right. Apparently,seems that it is an overconstrained problem which needs special attention and detailed custom moves (i have not developed any custom move,yet) and/or tweaking of weights and maybe redefinition of some constraints. I am not sure and i can't find a way out. Here are the problem details:
- 365 days (or at least 180 days)
- Each day has 2 shifts Day and Night
- 25 pharmacies (with no special skills) divided in 2 groups:
- Group A contains zone1 Pharmacies
- Group B contains zone2 Pharmacies
- 3 Pharmacies have the same address (members of the same group B) but are considered independent.
Constraints
- One shift per day for employees Hard constraint
- Min and Max number of Day Shifts, Night Shifts and Total Assignments fairly distributed.Soft Constraint.
- Alternate shift pattern(D-N or N-D) ->unwanted patterns (N-N) and (D-D) Hard constraint
- minimum free days between workdays Soft Constraint
- no consecutive workdays Hard constraint
- Zone coverage: DAY and NIGHT shifts should be assigned to 1 pharmacy from each zone .Soft Constraint
- For same address employees: No 2 assignments in the same day Hard constraint,time between them = 3 days (Hard constraint but if needed for problem relaxation could be Soft constraint)
From input file:dataset.xml
<Contract ID="0"><Description>fulltime</Description>
<SingleAssignmentPerDay weight="1">true</SingleAssignmentPerDay><MaxNumAssignments on="1" weight="1">13</MaxNumAssignments><MinNumAssignments on="1" weight="1">11</MinNumAssignments><MaxNumDayAssignments on="1" weight="1">7</MaxNumDayAssignments>
<MinNumDayAssignments on="1" weight="1">5</MinNumDayAssignments>
<MaxNumNightAssignments on="1" weight="1">7</MaxNumNightAssignments>
<MinNumNightAssignments on="1" weight="1">5</MinNumNightAssignments>
<MaxConsecutiveWorkingDays on="1" weight="1">1</MaxConsecutiveWorkingDays><MinConsecutiveWorkingDays on="0" weight="1">1</MinConsecutiveWorkingDays> <MaxConsecutiveFreeDays on="1" weight="1">12</MaxConsecutiveFreeDays>
<MinConsecutiveFreeDays on="1" weight="4">5</MinConsecutiveFreeDays>
<UnwantedPatterns>
<Pattern>0</Pattern>
<Pattern>1</Pattern>
</UnwantedPatterns>
</Contract>
Where Pattern{0,1}={(DAY,DAY),(NIGHT,NIGHT)}`
RULES
rule "oneShiftPerDay"
dialect "mvel"
when
$leftAssignment : ShiftAssignment($leftId : id, $pharmacy : pharmacy, $shiftDate : shiftDate, pharmacy != null)
$rightAssignment : ShiftAssignment(pharmacy == $pharmacy, shiftDate == $shiftDate, id > $leftId)
then
scoreHolder.addHardConstraintMatch( kcontext, -10);
end
rule "insertPharmacyAssignmentTotal"
salience 2 // Do these rules first (optional, for performance)
dialect "mvel"
when
MinMaxContractLine(contractLineType == ContractLineType.TOTAL_ASSIGNMENTS, enabled == true,$contract : contract)
$pharmacy : Pharmacy(contract == $contract)
$assignmentTotal : Number() from accumulate(
$assignment : ShiftAssignment(pharmacy == $pharmacy,$sdi1:shiftDateDayIndex),
count($assignment)
)
then
insertLogical(new PharmacyAssignmentTotal($pharmacy, $assignmentTotal.intValue()));
end
rule "insertPharmacyWorkSequence"
salience 1 // Do these rules first (optional, for performance)
when
PharmacyConsecutiveAssignmentStart(
$pharmacy : pharmacy,
$firstDayIndex : shiftDateDayIndex
)
PharmacyConsecutiveAssignmentEnd(
pharmacy == $pharmacy,
shiftDateDayIndex >= $firstDayIndex,
$lastDayIndex : shiftDateDayIndex
)
// There are no free days between the first and last day
not PharmacyConsecutiveAssignmentEnd(
pharmacy == $pharmacy,
shiftDateDayIndex >= $firstDayIndex && < $lastDayIndex
)
then
insertLogical(new PharmacyWorkSequence($pharmacy, $firstDayIndex, $lastDayIndex));
end
rule "insertFirstPharmacyFreeSequence"
salience 1 // Do these rules first (optional, for performance)
when
PharmacyConsecutiveAssignmentStart(
$pharmacy : pharmacy,
$lastDayIndexPlusOne : shiftDateDayIndex
)
// There are no working days before the first day
not PharmacyConsecutiveAssignmentEnd(
pharmacy == $pharmacy,
shiftDateDayIndex < $lastDayIndexPlusOne
)
PharmacyRosterInfo(firstShiftDateDayIndex < $lastDayIndexPlusOne, $firstDayIndex : firstShiftDateDayIndex)
then
insertLogical(new PharmacyFreeSequence($pharmacy, $firstDayIndex, $lastDayIndexPlusOne - 1));
end
rule "insertLastPharmacyFreeSequence"
salience 1 // Do these rules first (optional, for performance)
when
PharmacyConsecutiveAssignmentEnd(
$pharmacy : pharmacy,
$firstDayIndexMinusOne : shiftDateDayIndex
)
// There are no working days after the last day
not PharmacyConsecutiveAssignmentStart(
pharmacy == $pharmacy,
shiftDateDayIndex > $firstDayIndexMinusOne
)
PharmacyRosterInfo(lastShiftDateDayIndex > $firstDayIndexMinusOne, $lastDayIndex : lastShiftDateDayIndex)
then
insertLogical(new PharmacyFreeSequence($pharmacy, $firstDayIndexMinusOne + 1, $lastDayIndex));
end
rule "insertEntirePharmacyFreeSequence"
salience 1 // Do these rules first (optional, for performance)
when
$pharmacy : Pharmacy()
// There are no working days after the last day
not PharmacyConsecutiveAssignmentStart(
pharmacy == $pharmacy
)
PharmacyRosterInfo($firstDayIndex : firstShiftDateDayIndex, $lastDayIndex : lastShiftDateDayIndex)
then
insertLogical(new PharmacyFreeSequence($pharmacy, $firstDayIndex, $lastDayIndex));
end
rule "insertPharmacyFreeSequence"
salience 1 // Do these rules first (optional, for performance)
when
PharmacyConsecutiveAssignmentEnd(
$pharmacy : pharmacy,
$firstDayIndexMinusOne : shiftDateDayIndex
)
PharmacyConsecutiveAssignmentStart(
pharmacy == $pharmacy,
shiftDateDayIndex > $firstDayIndexMinusOne,
$lastDayIndexPlusOne : shiftDateDayIndex
)
// There are no working days between the first and last day
not PharmacyConsecutiveAssignmentStart(
pharmacy == $pharmacy,
shiftDateDayIndex > $firstDayIndexMinusOne && < $lastDayIndexPlusOne
)
then
insertLogical(new PharmacyFreeSequence($pharmacy, $firstDayIndexMinusOne + 1, $lastDayIndexPlusOne - 1));
end
rule "Minimum and Maximum total assignments"
salience 1
no-loop
when
$contractLine : MinMaxContractLine(
contractLineType == ContractLineType.TOTAL_ASSIGNMENTS, maximumEnabled == true,
$contract : contract, $maximumValue : maximumValue
)
$pharmacy: Pharmacy(contract == $contract)
accumulate(
$assignment : ShiftAssignment($pharmacy == pharmacy);
$total : count($assignment)
)
then
int totalInt = $total.intValue();
if (totalInt < $contractLine.getMinimumValue()) {
scoreHolder.addSoftConstraintMatch(kcontext,
(totalInt - $contractLine.getMinimumValue()) * $contractLine.getMinimumWeight());
helperWithMessage(drools,"minimum total ass for "+$pharmacy.getName()+" is "+$contractLine.getMinimumValue()+" > "+totalInt);
} else if (totalInt > $contractLine.getMaximumValue()) {
scoreHolder.addSoftConstraintMatch(kcontext,
($contractLine.getMaximumValue() - totalInt) * $contractLine.getMaximumWeight());
helperWithMessage(drools,"maximum total ass for "+$pharmacy.getName()+" is "+$contractLine.getMaximumValue()+" < "+totalInt);
} else {
// Workaround for https://issues.redhat.com/browse/PLANNER-761
scoreHolder.addSoftConstraintMatch(kcontext, 0);
}
end
rule "Minimum and maximum number of day service assignments"
dialect "mvel"
when
$contractLine : MinMaxContractLine(contractLineType == ContractLineType.TOTAL_DAY_ASSIGNMENTS, enabled == true,
$contract : contract)
$pharmacy: Pharmacy(contract == $contract)
accumulate(
$assignment : ShiftAssignment($pharmacy == pharmacy,$shiftType:shift.getShiftType,$shiftType.toString=="DAY");
$total : count($assignment)
)
then
int totalInt = $total.intValue();
if ($contractLine.isMinimumEnabled() && totalInt < $contractLine.getMinimumValue()) {
scoreHolder.addSoftConstraintMatch(kcontext,
(totalInt - $contractLine.getMinimumValue()) * $contractLine.getMinimumWeight());
} else if ($contractLine.isMaximumEnabled() && totalInt > $contractLine.getMaximumValue()) {
scoreHolder.addSoftConstraintMatch(kcontext,
($contractLine.getMaximumValue() - totalInt) * $contractLine.getMaximumWeight());
} else {
// Workaround for https://issues.redhat.com/browse/PLANNER-761
scoreHolder.addSoftConstraintMatch(kcontext, 0);
}
end
rule "Minimum and maximum number of night service assignments"
dialect "mvel"
when
$contractLine : MinMaxContractLine(contractLineType == ContractLineType.TOTAL_NIGHT_ASSIGNMENTS, enabled == true,
$contract : contract)
$pharmacy: Pharmacy(contract == $contract)
$total : Number() from accumulate(
$assignment : ShiftAssignment($pharmacy == pharmacy,$shiftType:shift.getShiftType,$shiftType.toString=="NIGHT");
count($assignment)
)
then
int totalInt = $total.intValue();
if ($contractLine.isMinimumEnabled() && totalInt < $contractLine.getMinimumValue()) {
scoreHolder.addSoftConstraintMatch(kcontext,
(totalInt - $contractLine.getMinimumValue()) * $contractLine.getMinimumWeight());
} else if ($contractLine.isMaximumEnabled() && totalInt > $contractLine.getMaximumValue()) {
scoreHolder.addSoftConstraintMatch(kcontext,
($contractLine.getMaximumValue() - totalInt) * $contractLine.getMaximumWeight());
} else {
// Workaround for https://issues.redhat.com/browse/PLANNER-761
scoreHolder.addSoftConstraintMatch(kcontext, 0); helper(drools);
}
end
rule "minimumConsecutiveFreeDays"
when
$contractLine : MinMaxContractLine(
contractLineType == ContractLineType.CONSECUTIVE_FREE_DAYS, minimumEnabled == true,
$contract : contract, $minimumValue : minimumValue
)
$pharmacy : Pharmacy(contract == $contract)
$pharmacyFreeSequence : PharmacyFreeSequence(
pharmacy == $pharmacy,
dayLength < $minimumValue,
$dayLength : dayLength
)
then
scoreHolder.addHardConstraintMatch(kcontext,($dayLength-$minimumValue )* $contractLine.getMinimumWeight());
end
rule "maxConsecutiveWorkingDays"
when
$contractLine : MinMaxContractLine(
contractLineType == ContractLineType.CONSECUTIVE_WORKING_DAYS, maximumEnabled == true,
$contract : contract, $maximumValue : maximumValue
)
PharmacyWorkSequence(
getPharmacy().getContract() == $contract,
dayLength > $maximumValue,
$dayLength : dayLength
)
then
scoreHolder.addHardConstraintMatch(kcontext, ($maximumValue - $dayLength) * $contractLine.getMaximumWeight());
end
rule "maximumConsecutiveFreeDays"
when
$contractLine : MinMaxContractLine(
contractLineType == ContractLineType.CONSECUTIVE_FREE_DAYS, maximumEnabled == true,
$contract : contract, $maximumValue : maximumValue
)
$pharmacy : Pharmacy(contract == $contract)
$pharmacyFreeSequence : PharmacyFreeSequence(
pharmacy == $pharmacy,
dayLength > $maximumValue,
$dayLength : dayLength
)
then
scoreHolder.addHardConstraintMatch(kcontext,($maximumValue - $dayLength )* $contractLine.getMaximumWeight()); helper(drools);
end
rule "insertPharmacyConsecutiveAssignmentStart"
salience 2 // Do these rules first (optional, for performance)
when
ShiftAssignment(
$pharmacy : pharmacy, pharmacy != null,
$dayIndex : shiftDateDayIndex,
$shiftDate : shiftDate
)
// The first day has no working day before it
not ShiftAssignment(pharmacy == $pharmacy, shiftDateDayIndex == ($dayIndex - 1))
then
insertLogical(new PharmacyConsecutiveAssignmentStart($pharmacy, $shiftDate));
end
rule "insertPharmacyConsecutiveAssignmentEnd"
salience 2 // Do these rules first (optional, for performance)
when
ShiftAssignment(
$pharmacy : pharmacy, pharmacy != null,
$dayIndex : shiftDateDayIndex,
$shiftDate : shiftDate
)
// The last day has no working day after it
not ShiftAssignment(pharmacy == $pharmacy, shiftDateDayIndex == ($dayIndex + 1))
then
insertLogical(new PharmacyConsecutiveAssignmentEnd($pharmacy, $shiftDate));
end
rule "sameAddress4DaysFree"
dialect "mvel"
when
$leftAssignment : ShiftAssignment($leftPharmacy : pharmacy,$leftCode:pharmacy.getCode, $ldi : shiftDate.dayIndex, $leftAddress:pharmacy.getAddress(), pharmacy != null)
ShiftAssignment($rightPharmacy:pharmacy,pharmacy.getAddress()==$leftAddress,$rightPharmacy.getCode()!=$leftCode,$sdi:shiftDateDayIndex,$sdi == $ldi,pharmacy != null)
or ShiftAssignment($rightPharmacy:pharmacy,$rightPharmacy.getAddress()==$leftAddress,$rightPharmacy.getCode()!=$leftCode,$sdi:shiftDateDayIndex,$sdi == $ldi+1,pharmacy != null)
or ShiftAssignment($rightPharmacy:pharmacy,$rightPharmacy.getAddress()==$leftAddress,$rightPharmacy.getCode()!=$leftCode,$sdi:shiftDateDayIndex,$sdi == $ldi+2,pharmacy != null)
or ShiftAssignment($rightPharmacy:pharmacy,$rightPharmacy.getAddress()==$leftAddress,$rightPharmacy.getCode()!=$leftCode,$sdi:shiftDateDayIndex,$sdi == $ldi+3,pharmacy != null)
or ShiftAssignment($rightPharmacy:pharmacy,$rightPharmacy.getAddress()==$leftAddress,$rightPharmacy.getCode()!=$leftCode,$sdi:shiftDateDayIndex,$sdi == $ldi+4,pharmacy != null)
then
int penalty=$sdi-$ldi;
scoreHolder.addHardConstraintMatch( kcontext, -4/penalty);
end
rule "alternateShiftTypes"
when
$contractLine : MinMaxContractLine(
contractLineType == ContractLineType.CONSECUTIVE_SAME_SHIFT_TYPE, maximumEnabled == true,
$contract : contract, $maximumValue : maximumValue
)
ShiftAssignment($pharmacy : pharmacy, $pharmacy != null,$shiftDate1:shiftDate,$dayIndex1:shiftDateDayIndex,$ShiftType1:shiftType, contract == $contract)
ShiftAssignment($pharmacy== pharmacy,$dayIndex2:shiftDateDayIndex,$shiftDate2:shiftDate,$dayIndex2>$dayIndex1,$ShiftType2:shiftType
,$ShiftType2!=$ShiftType1)
not ShiftAssignment($pharmacy== pharmacy,$dayIndex3:shiftDateDayIndex,$dayIndex3>$dayIndex1,
$dayIndex3<$dayIndex2)
then
scoreHolder.addHardConstraintMatch( kcontext, 1);
end
rule "ZoneCoverage"
when
$leftAssignment : ShiftAssignment($leftId :id, $leftPharmacy : pharmacy,$leftCode:pharmacy.code, $leftShiftDate : shiftDate, $leftCentral:pharmacy.getCentral, pharmacy != null)
$rightAssignment : ShiftAssignment(id > $leftId, $rightPharmacy : pharmacy,$rightPharmacy !=$leftPharmacy, shiftDate == $leftShiftDate,$leftCentral==pharmacy.getCentral, pharmacy != null)
then
scoreHolder.addSoftConstraintMatch(kcontext,-1);
end
rule "evenlyDistributeTotalAssignments"
dialect "mvel"
when
$sum: Number() from
accumulate(PharmacyAssignmentTotal($pharmacy:pharmacy,$assignmentTotal:total),sum($assignmentTotal))
$sumSquared:Number() from accumulate(PharmacyAssignmentTotal($assignmentTotal:total),sum(squaredValue($assignmentTotal))
)
then
getFairnessValue($sum.intValue(),$sumSquared.intValue()));
scoreHolder.addSoftConstraintMatch(kcontext,-1*getFairnessValue($sum.intValue(),$sumSquared.intValue()));
end
rule "unwantedPatternShiftType2DaysPattern"
when
$pattern : ShiftType2DaysPattern(
$dayIndex0ShiftType : dayIndex0ShiftType,
$dayIndex1ShiftType : dayIndex1ShiftType
)
PatternContractLine(
pattern == $pattern, $contract : contract
)
ShiftAssignment(
shiftType == $dayIndex0ShiftType,
contract == $contract,
$pharmacy : pharmacy, $firstDayIndex : shiftDateDayIndex
)
ShiftAssignment(shiftType == $dayIndex1ShiftType,pharmacy == $pharmacy,
$dayIndex2:shiftDateDayIndex,$dayIndex2 > $firstDayIndex )
not ShiftAssignment($pharmacy== pharmacy,$dayIndex3:shiftDateDayIndex,$dayIndex3>$firstDayIndex,
$dayIndex3<$dayIndex2)
then
scoreHolder.addHardConstraintMatch(kcontext,-1);
end
No matter what i do,i get no good solutions.Could be a conflict betweeen the 2 constraints freesequence and the freedays of the same address pharmacies? Performance is terrible and i see that the solver gets stuck in local minima. Any ideas?