Re: [rules-users] Optaplanner order schedule performance problem

Geoffrey De Smet Wed, 20 Nov 2013 23:55:32 -0800

I don't have the time budget to do a full code review for a community question,
but here are my initial thoughts:

A) Is your average calculation count per second above 5000?
If not, figure out which score rules are slowing you down.

B) Your assessment of "Concept with timeslots has to many possible order positions." might be correct.

I've seen before on job shop scheduling problems,
that having second grained accuracy on starting time, in cases with days/weeks of running time,
where each job (=order) takes minutes - is inefficient in a straightforward model, currently.
Specifically because the constraints want the jobs to be pasted after each other.

Here are (parts of) a solution for B):

1) Use a smarter (more complex model) that leaves less pointless combinations.
Some idea's:
- Look at the Project Job Scheduling example's source code.
http://www.youtube.com/watch?v=_2zweB9JD7c
If orders have dependencies on each other, this works well.
- Look at Vehicle Routing with Time windows. Maybe this model works for you:
Each Vehicle = 1 of your machines. Each customer = 1 job. ArrivalTime = startingOrderTime.
Setup times etc are added automatically in the arrivalTime due to the VariableListener.

2) (Future) For OptaPlanner 6.1.0.Beta1 (which is coming soon), we are working on numeric ValueRanges.
https://issues.jboss.org/browse/PLANNER-160
This way, if a the values are (00:01, 00:02, 00:03, ..., 00:55, ...),
OptaPlanner understands that 00:02 is closer to 00:03 than to 00:55,
and the generic change move selector will support a gaussian distribution random close to it's current value.

3) (Future) "CH based metaheuristics" (also called "indirect metaheuristics" - or by me "feature L").
Too hard to explain now, but research shows this is very promising for these kind of use cases (a big leap forward).
I am confident I can make it simple to use (despite it's inherit complexity), hopefully for 6.1.
It does have some drawbacks and limitations (especially if you rely on a specific types of soft constraints).

On 20-11-13 17:32, Mohr, Michael wrote:

Hi,

I must find start and end times for orders on different equipment’s in requirement of a stock.
What can I do better to get faster a solution.

I read the forum entries but it don't helps.
- Scheduling events with varying durations - corrupted score
- Time Slots vs Time Periods

Graphics and detail description in the pdf.

Domain model

@PlanningEntity
EquipmentAllocation has a Equipment
EquipmentAllocation has a Order
EquipmentAllocation has a TimeSlot
------------------------------------------------------
@PlanningVariable
Order
Attribute: quantity
------------------------------------------------------
TimeSlot
Attribute: startTime, endTime, duration, sequenceNumber
------------------------------------------------------
Material
Attribute: stock, minStock, maxStock
------------------------------------------------------
Material Demand has a TimeSlot
Attribute: quantity
------------------------------------------------------

Conditions:
- Order is executable on each equipment.
- Orders has different sizes.
- Order running time is depending of the material and the equipment.
- Gaps between orders are possible if there is no demand.
- Gaps between orders are possible when there is a equipment setup time.
- Parallel orders with same material on different equipment’s are possible.

Target:
- Calculate start and endtims for an order.
- Start and endtime is precisely one minute (maximum five minutes if runtime is to long).
- Satisfy only the demand of a material.
- Good result in 5 minutes.
- No exceed min or max stock.

Plan data:
- Plan for 24 hours.
- Plan 35 orders (normal order time is 2 hours).
- Plan 5 demands with different materials (7 orders per demand).
- Plan 3 equipment’s.

Problem:
- No result in 5 minutes.
- Concept with timeslots has to many possible order positions.
- No restrictions are possible to find the best solution.

Use a pillar swap to create the possible order positions on each equipment.
Use a pillar swap to lay the order over a lot of timeslots on a equipment.

Example:
- 1 order (with 2 hours)
- 1 equipment
- 24 hours planning time with 1 timeslot per minute
- Possible order positions = 22 * 60 = 1320 (on one equipment)
- Possible order positions = 1320 * 3 = 3960 (on three equipment)
- Possible order positions = 3960 * 35 = 138.600 (all orders on all equipment)

rule "Check order not allocate to less."

when
$f : Order( $quantity : quantity , $m : material )

$result : Number( (intValue > 0) && ( intValue < $quantity ) )
from accumulate(
EquipmentAllocation( order != null && order == $f , $sp : equipment.speedMap ),
   sum($sp.get($m))
)
then
int hard = $result.intValue() - $quantity;
scoreHolder.addHardConstraintMatch(kcontext, hard );
end

rule "Check order not allocate to many."

when
$f : Order( $quantity : quantity , $m : material )

$result : Number( (intValue > 0) && ( intValue > $quantity ) )
from accumulate(
EquipmentAllocation(order != null && order == $f , $map : equipment.orderMap )
sum( $map.get( $f ))
)
then
int hard = $quantity - $result.intValue();
scoreHolder.addHardConstraintMatch(kcontext, hard );
end

rule "Check demand"

when
$m : Material( $stock : stock )

$t : TimeSlot( $sequence : sequence )

$sumDemand : Number( )
from accumulate (
   Demand ( timeSlot.sequence <= $sequence , material == $m , $quantity : quantity )
   sum( $quantity )
)

$sumAllocation : Number( ($stock + intValue - $sumDemand.intValue()) < 0 )
from accumulate (
   EquipmentAllocation( (order != null && order.material == $m) , timeSlot.sequence <= $sequence , $sp : equipment.speedMap),
sum( $sp.get($m) )
)
then
scoreHolder.addHardConstraintMatch(kcontext, -1);
end

rule "Check min stock"

when
$m : Material( $stock : stock , $minStock : minStock, $maxStock : maxStock )

$t : TimeSlot( $sequenceT : sequence )

$sumDemand : Number( )
from accumulate (
   Demand ( timeSlot.sequence <= $sequenceT , material == $m , $quantityDemand : quantity )
   sum( $quantityDemand )
)

$sumAllocation : Number( ($stock + (intValue) - $sumDemand.intValue()) < $minStock )
from accumulate (
   EquipmentAllocation( order != null , order.material == $m , timeSlot.sequence <= $sequenceT , $sp : equipment.speedMap ),
sum( $sp.get($m) )
)
then
scoreHolder.addHardConstraintMatch(kcontext, -1);
end

rule "Check max stock"

when
$t : TimeSlot( $sequence : sequence )

$m : Material( $stock : stock , $maxStock : maxStock )

$sumDemand : Number( )
from accumulate (
   Demand ( timeSlot.sequence <= $sequence , material == $m, $quantityDemand : quantity)
   sum( $quantityDemand )
)

$sumAllocation : Number( ($stock + intValue - $sumDemand.intValue()) > $maxStock )
from accumulate (
   EquipmentAllocation( (order != null && order.material == $m) , timeSlot.sequence <= $sequence , $sp : equipment.speedMap ),
sum( $sp.get($m) )
)
then
scoreHolder.addHardConstraintMatch(kcontext, -1);
end

Gruß

Michael Mohr
Software Engineer

CONFIDENTIALITY : This e-mail and any attachments are confidential and may be privileged. If you are not a named recipient, please notify the sender immediately and delete the e-mail from your system. You are not authorized to disclose the contents to another person, to use it for any purpose or store or copy the information in any medium.
_______________________________________________
rules-users mailing list
[email protected]
https://lists.jboss.org/mailman/listinfo/rules-users

_______________________________________________
rules-users mailing list
[email protected]
https://lists.jboss.org/mailman/listinfo/rules-users

Re: [rules-users] Optaplanner order schedule performance problem

Reply via email to