The paint shop problem
Painting is a bottleneck in truck production. Painting a truck takes 3 minutes, but if the booth holds a different color it first has to flush out the old paint and refill, which takes another 3 minutes and wastes paint. The scheduler has two goals: finish all trucks quickly (makespan) and keep the number of flushes low.
Orders arrive in real time and booths break down without warning, so a schedule computed in advance does not hold up. Both rules in the paper decide online, one truck at a time, using only local information from each booth.
- 20 colors
- one per truck, fixed by the customer order, plus a priority from 1 to 100
- 6 to 15 booths
- each with a queue of at most 5 trucks
- 3 + 3 minutes
- paint time, plus flush time whenever the color changes
- 1 in 20
- chance per minute that one random booth goes down for 0 to 20 minutes
- 420 minutes
- of arrivals, the equivalent of a seven hour shift
Trucks queued at a booth that goes down cannot be moved and wait for the repair. If no booth can accept a truck it goes to temporary storage, which the paper counts as a failure of the system.
Two rules for choosing a booth
Under both rules every available booth computes one number for the truck that just left the line, and the highest number wins. A booth that is down or has a full queue stays out. The rules differ in what goes into that number.
Market rule: booths bid
The authors' own version of Morley's scheduler, which ran in a real truck factory. Details of the original are protected.
- ci,k is 1 if the last truck in booth k's queue has the color truck i needs, otherwise 0.
- ΔT is the wait before the truck would be painted: 3 minutes per queued truck, 3 per color change already in the queue, plus the time left on the current job.
- P, C and L weigh priority, color match and waiting time.
Ant rule: booths respond to demand
Based on the response threshold model of division of labor in insect colonies.
- D is the demand for color c: the summed priority of all unassigned trucks of that color.
- θk,c is booth k's threshold for color c. A low threshold means a strong response.
- Learning: the winning booth lowers its threshold for that color by ξ, every other booth raises its own by φ, within [θmin, θmax].
Where the ant rule comes from
In a colony, workers with a low response threshold for a task react to weaker stimuli than workers with a high threshold. Doing the task reduces the stimulus, so high-threshold workers only step in when the low-threshold workers are missing or overwhelmed. Wilson (1984) saw this in Pheidole ants: when he lowered the share of minor workers, the large-headed majors took on the minors' tasks, and activity rates shifted within an hour.
Adding reinforcement turns identical individuals into specialists: performing a task lowers the threshold for it, not performing it raises the threshold. In the paint shop, a booth that keeps taking black trucks becomes the booth that responds first to black.
Note: the 1998 model behind the ant rule
The ant rule is an adaptation of the model in Theraulaz, Bonabeau and Deneubourg, "Response threshold reinforcement and division of labour in insect societies", Proc. R. Soc. Lond. B 265, 327-332 (1998). Two of the three authors of that paper are also authors of the scheduling paper, which cites it for the learning step.
In the 1998 model, worker i engages in task j with a probability that depends on the stimulus intensity sj and the worker's threshold θij. The threshold then moves with experience, inside fixed bounds:
The paper shows that this loop turns initially identical workers into specialists: a worker that happens to perform a task becomes more sensitive to it, performs it more, and keeps the stimulus low enough that the others rarely respond and drift away from it. It also predicts that if specialists are removed long enough, their replacements stay specialized after the originals return, which fixed thresholds or aging alone would not produce.
| 1998 insect model | 2001 paint shop rule |
|---|---|
| Worker i, task j | Booth k, paint color c |
| Stimulus sj, which grows while the task goes undone | Demand D, the summed priority of unassigned trucks of that color |
| Response s2 / (s2 + θ2) | Same form, with a weight α on the threshold and an added term β · ΔT 2 so that a long queue lowers the response |
| The response is a probability of engaging in the task | Responses are compared and the booth with the largest one takes the truck |
| Learning: θ falls by ξ per unit time spent on the task | θ falls by ξ each time the booth wins a truck of that color |
| Forgetting: θ rises by φ per unit time not spent on the task | θ rises by φ each time another booth wins a truck of that color |
| Bounds [θmin, θmax], for example 1 to 1000 | Same bounds, with values chosen by the genetic algorithm |
The symbols ξ, φ, θmin and θmax are carried over unchanged. The 1998 example uses slow forgetting relative to learning (ξ = 10, φ = 1), while the genetic algorithm in the scheduling paper settled on faster forgetting than learning (ξ = 7.85, φ = 17.73). The heatmap in the simulation below shows the resulting specialization of booths by color.
The same mechanism under two vocabularies
| Market | Ant colony | In the paint shop |
|---|---|---|
| Bidding high | Having a low threshold | The booth is likely to take the truck |
| Tasks offered for auction | Stimuli that signal work to be done | Trucks leaving the line, weighted by priority |
| Market clearing | All tasks get performed | Every truck is assigned and painted |
| A black booth bids low for a white truck but can still win it | Majors do not do brood care unless minors are not doing it | A poorly matched booth takes the truck when no better booth is free |
| Bids adjusted after wins and losses | Thresholds reinforced by doing or not doing the task | Booths drift toward the colors they have been painting |
Run the paint shop
Both shops below receive the same trucks in the same order and suffer the same breakdowns. Only the dispatch rule differs. This is a reimplementation written for this page from the paper's description, so its numbers will not match the paper's tables. See the notes at the end of this section.
Flushes so far
Ant thresholds: who specializes in what
One row per booth, one column per color. A strongly colored cell is a low threshold, meaning the booth responds strongly to that color.
Parameters and modeling choices
Sliders span the search ranges of the paper's Table 1 and start at the best values found by its genetic algorithm (Table 2). Changing a value restarts the run with the same truck sequence.
Market rule
Ant rule
Choices made for this reimplementation
- With ΔT = 0 the market bid divides by zero. The setting above picks how that is handled. It changes the market rule's flush count a lot, which fits the authors' warning that the comparison rests on ad hoc choices.
- Ant thresholds start at the midpoint of [θmin, θmax]. The paper does not give starting values.
- Each booth starts loaded with a color drawn from the order distribution. The first truck of another color costs a flush.
- A truck that needs a flush stays in the queue during the flush and counts toward the limit of 5.
- Breakdown durations are whole minutes from 0 to 20. A booth that is down pauses its current job.
- Each minute: breakdown event, then dispatch of new trucks, then dispatch of trucks in storage, then booths work.
- Table 2's parameter values were tuned for the authors' simulator, not this one, so neither rule is at its best here.
Repeat the experiment
A single run depends on the luck of the truck sequence. The paper averages 1000 runs per configuration. This button runs 200 paired runs with the settings chosen above (test set, booth count, parameters) and summarizes them.
| Flushes mean ± sd | Time after last truck mean ± sd | Runs using storage |
|---|
Distribution of flushes per run
What the paper reports
Each configuration was run 1000 times with the parameters from the genetic algorithm. Tables start at the smallest booth count for which storage was never needed. Bars show means, whiskers show one standard deviation. Values are from Tables 3 to 6 of the paper.
How the authors read these results
- Makespan is comparable under both rules in all four test sets.
- Where the ant rule does better, it is on the number of flushes, which the authors attribute to booths specializing in colors.
- The differences in flushes are reported as significant for test sets 1 and 3 (t-test, df = 998, P < 0.01) and as comparable for test sets 2 and 4.
- Specialization could be added to the market rule as well, under a different vocabulary.
- The comparison is meant to show how similar the two approaches are, not that one is better. The authors say the comparison itself should not be considered significant because of the many ad hoc choices, and that more testing is needed.
- Both rules beat the fixed, statistics-based schedule the factory used before, under which the number of flushes ended up almost as large as the number of trucks.
- For the real factory deployment of the market-based system, the paper cites a 10% reduction in paint use, half as many paint changeovers, higher throughput and shorter code than the earlier pre-optimized schedule.
How the parameters were found
Both rules have free weights: three for the market rule, six for the ant rule. The authors searched for good values with the same genetic algorithm for both.
- Start with 50 random individuals. Each parameter is coded as 8 bits, giving a genome of 24 bits (market) or 48 bits (ant).
- Score each individual over 30 simulation runs. For the first 50 generations fitness is 1000 minus the time steps beyond 420 needed to paint the last truck. After that, the number of flushes is subtracted as well. Speed comes first, paint savings second.
- Hold tournaments: draw two individuals at random and copy the fitter one into the next generation with 75% probability, otherwise the less fit one. Repeat until the population is full.
- Pair individuals at random and, with 75% probability, swap their genomes up to a random crossover point.
- Flip each bit with probability 0.3%.
- Repeat for 100 generations and keep the fittest individual.
Search ranges and best values
The mark shows where the best value (Table 2) falls inside its search range (Table 1).
| Parameter | Range | Best | Position in range |
|---|