APS开源源码解读: 排程工具 optaplanner II

上篇

排产，原则上也就是分配时间，分配资源；保证资源日历约束，保证工艺路线约束。我们看一下如何实现optaplanner 优化的

• 定义一个move, 一个move可能改变了分配到的资源，也可能改变了一个资源上的顺序。改变即意味着优化的可能
• 原本分配的资源，把后工序移到前面来。前后各算一个score. 通过socreDirector中定义的beforeVariableChanged/afterVariableChanged
• 再更新另一个资源上的链，同时前后继续scoreDirector触发
• 另一个shadow variable: Start time，通过StartTimeUpdatingVariableListener触发改变。这里的改变保证了不同资源上的job满足工艺路线的约束

模型

如何建模对一个优化问题非常关键

Chain Structure:

The previousAllocation can now be either a Resource (anchor) or another Allocation
Resource becomes a shadow variable automatically updated based on the chain
This creates a clean chain: Resource -> Allocation1 -> Allocation2 -> …

Move Simplification:

No need for separate resource change moves
Single ChainChangeMove handles both resource changes and sequence changes
When moving to a different resource, just set the previous to be the resource
When moving within same resource, set previous to be another allocation

Benefits:

Simpler code structure
Fewer variables to maintain
More efficient move generation
Better encapsulation of the chaining logic
Automatic resource updates through shadow variable

过程

本文我们继续试图学习optaplanner来进行排产规划。

When a move changes an allocation’s resource and/or sequence:

When OptaPlanner/timefold selects a move:

1. Check if move is doable (isMoveDoable)

• Verify resource compatibility
• Check for circular dependencies
• Validate sequence constraints

2. Execute the move (doMove)

• Update primary planning variables
• Shadow variable listener triggers
• Start/end times cascade update

3. Score calculation

• Check hard constraints
  • Resource conflicts
  • Job dependencies
  • Resource compatibility
• Evaluate soft constraints
  • Makespan
  • Setup times
  • Resource preferences

4. Accept/Reject move based on score

• If better: keep change
• If worse: maybe keep (based on meta-heuristic)

The previousAllocation shadow variable is updated first
This triggers the AnchorShadowVariable (resource) to update
The StartTimeUpdatingVariableListener then recalculates timing

Chain Update Process:

When an allocation moves to a new resource:
a. It disconnects from its old chain (previous/next allocations are relinked)
b. Inserts into new resource’s chain at specified position
c. Updates shadow variables (resource, start time) for moved allocation
d. Recursively updates all downstream allocations in both chains

Impact on Route Dependencies:

The StartTimeUpdatingVariableListener ensures timing consistency
When start time changes, it propagates updates down the chain
If jobs have dependencies across resources, you’ll need additional constraints
Can add precedence constraints between related jobs

例如

Before:
Resource1 -> Allocation1 -> Allocation2 -> Allocation3
Resource2 -> Allocation4 -> Allocation5

After:
Resource1 -> Allocation1 -> Allocation3
Resource2 -> Allocation4 -> Allocation2 -> Allocation5

The system will:

Update Allocation2’s previousAllocation to Allocation4
Update Allocation2’s resource to Resource2
Recalculate start times for Allocation2 and all subsequent allocations
Update Allocation3’s previousAllocation to Allocation1
Recalculate start times in Resource1’s chain

细节

当一个move发生的时候：

1. isMoveDoable() is checked
2. doMove() is called if move is doable
3. Score is calculated after each change
4. Move is accepted/rejected based on score

During doMove()

5. beforeVariableChanged() notifies ScoreDirector
6. Chain updates occur
7. afterVariableChanged() notifies ScoreDirector
8. Shadow variables update automatically
9. Score calculator runs automatically

Score calculation triggers:

10. After every genuine variable change
11. After shadow variables update
12. After variable listeners complete their updates
13. Before move acceptance/rejection decision

// Move implementation for changing position in chain
public class ChainChangeMove extends AbstractMove<JobShopSchedule> {
    private final Allocation allocation;
    private final Object newPrevious; // Can be Resource or Allocation
    
    @Override
    protected void doMoveOnGenuineVariables(ScoreDirector<JobShopSchedule> scoreDirector) {
        Object oldPrevious = allocation.getPreviousAllocation();
        Allocation nextAllocation = findNextAllocation(allocation);
        
        // Remove allocation from old chain position
        if (nextAllocation != null) {
            scoreDirector.beforeVariableChanged(nextAllocation, "previousAllocation");
            nextAllocation.setPreviousAllocation(oldPrevious);
            scoreDirector.afterVariableChanged(nextAllocation, "previousAllocation");
        }
        
        // Insert allocation at new chain position
        Allocation newNext = null;
        if (newPrevious instanceof Allocation) {
            newNext = findNextAllocation((Allocation) newPrevious);
        }
        
        // Update the moved allocation's previous
        scoreDirector.beforeVariableChanged(allocation, "previousAllocation");
        allocation.setPreviousAllocation(newPrevious);
        scoreDirector.afterVariableChanged(allocation, "previousAllocation");
        
        // Update the next allocation's previous if it exists
        if (newNext != null) {
            scoreDirector.beforeVariableChanged(newNext, "previousAllocation");
            newNext.setPreviousAllocation(allocation);
            scoreDirector.afterVariableChanged(newNext, "previousAllocation");
        }
    }
}

ScoreDirector manages this process

scoreDirector.beforeVariableChanged()
→ Make changes
→ scoreDirector.afterVariableChanged()
→ Shadow updates
→ Score calculation
→ Move acceptance

For chain moves specifically:

a. Original chain score is calculated
b. Move changes are applied
c. New chain score is calculated
d. Downstream impacts are scored
e. Total impact determines move acceptance