A maintenance team has six useful jobs and one short factory shutdown. The largest job has the greatest expected benefit. Several smaller jobs offer more benefit per minute. Neither ranking, by itself, tells the planner which complete set will fit and deliver the most value.
A 0-1 knapsack model answers that selection question. Each eligible job is either included or left out. The model chooses the set with the highest stated benefit while respecting a time limit. A second constraint can impose a spending limit. Dependencies and readiness restrictions can also be represented explicitly.
This article develops an original apparel-factory example and checks the result three ways: exhaustive enumeration, dynamic programming and integer optimization. It also shows why greedy rankings and rounded fractional answers can fail. All job times, costs and benefits are hypothetical teaching inputs. They are not maintenance standards, quotations or measured factory savings.
Establish which jobs the model may choose
Start with the technical maintenance decision. An optimization score cannot determine whether a required inspection or essential safeguard may be deferred. Separate mandatory work from genuinely optional work before calculating benefits. The team needs an approved list of tasks that can safely wait for another opportunity if they are not selected.
ApparelDiary's preventive and predictive maintenance guide covers how tasks should match failure modes and available evidence. The selection model begins after that review. It allocates scarce shutdown capacity among eligible jobs; it does not establish a machine's maintenance requirements.
For the teaching case, the shutdown lasts 480 minutes and has a total spending allowance of 1,500 currency units, or CU. Required work and common shutdown activities already reserve 120 minutes and 300 CU. The optional list therefore receives 360 minutes and 1,200 CU. These are separate resource limits.
The optional jobs use one crew in sequence. Their quoted durations include task-specific preparation, work and functional checks. Common activities belong in the earlier reserve and must not be counted again. If a job also needs another specialist, add that person's availability as a real constraint before adopting the result.
The US Department of Energy maintenance guide connects maintenance planning with equipment history, effective tasks and staff capability. It is a broad operations reference, not an apparel-specific rule for the numbers below. Actual task scope and access controls still require competent local review.
Put the candidate jobs on one consistent basis
Each row describes one indivisible work package. Its benefit is the expected production loss avoided over the same coming month, before subtracting the listed job cost. The example assumes those benefits are additive and do not overlap. Later sections show why those assumptions need checking.
Job | Equipment group | Duration, minutes | Job cost, CU | Expected benefit, CU |
A | Packing conveyor drive | 180 | 500 | 700 |
B | Fabric spreader feed | 120 | 400 | 520 |
C | Carton sealer rollers | 90 | 300 | 420 |
D | Press feed guides | 60 | 200 | 280 |
E | Thread trimming station | 150 | 350 | 600 |
F | Inspection conveyor | 120 | 300 | 450 |
The equipment descriptions identify the work packages. They do not prescribe a repair method or suggest that all tasks on those assets are optional. Each row is assumed to have a defined scope, ready parts, suitable tools and an approved work method before it enters the optimization.
A benefit of 700 CU is an appraisal input, not a promised cash receipt. The estimate should relate a credible change in failure exposure to a defined operational consequence. Show the horizon, evidence and cost boundary behind it. Avoid presenting an unsupported benefit to the nearest currency unit as if its precision proved its accuracy.
Keep cost and benefit distinct. The present objective maximizes expected avoided loss subject to a spending cap. Maximizing net benefit would use different objective coefficients. A decision to change that objective requires a new solve; subtracting cost from the selected plan afterward does not establish that it maximizes net return.
Translate the choice into binary variables
Let x(i) equal one when job i is selected and zero otherwise. Let v(i), t(i) and c(i) denote its benefit, minutes and cost. The base formulation is:
Maximize V = Σ v(i)x(i)
Σ t(i)x(i) ≤ 360
Σ c(i)x(i) ≤ 1,200
x(i) ∈ {0, 1}
The objective is measured in CU of expected benefit. The first constraint adds minutes; the second adds CU of spending. Neither may be combined with the other without an explicit conversion and a valid reason. Spending fewer CU does not create more shutdown minutes automatically.
The JuMP knapsack formulation uses the same binary selection structure. Here the capacity has an operational meaning: available crew time during one shutdown. The added budget row makes the model a knapsack problem with two resource dimensions.
Google's packing problem definitions distinguish multidimensional knapsack from multiple knapsacks. Two constraints on one shutdown are not two shutdowns. Assigning jobs among several separate shutdown windows would require assignment choices and a capacity for each window.
The base data happen to make the 1,200-CU budget nonbinding at the best solution. That does not justify deleting it from the planning record. The budget can become decisive after a price change, a smaller allowance or a different eligible task list.
Calculate and verify the best set
There are six binary decisions, giving 2⁶ = 64 possible subsets, including the empty set. Calculate total time, cost and benefit for every subset. Reject any set that exceeds either resource limit. Comparing the remaining thirty-four sets gives one highest-benefit result: jobs B, C and E.
Time(B,C,E) = 120 + 90 + 150 = 360 minutes
Cost(B,C,E) = 400 + 300 + 350 = 1,050 CU
Benefit(B,C,E) = 520 + 420 + 600 = 1,540 CU
The plan uses all optional time and leaves 150 CU of its optional budget. Including the reserved activities, total shutdown use is 480 minutes and total spending is 1,350 CU. The remaining money cannot buy another listed job because none fits in the zero remaining minutes.
For comparison, A, B and D also use 360 minutes. They cost 1,100 CU and offer benefit of 1,500. Their combination is feasible, but it trails the best set by forty CU of expected benefit. A small advantage deserves attention to input uncertainty; exact arithmetic does not make a fragile appraisal robust.
The result has been checked with an independent mixed-integer solver as well as enumeration. Both return B, C and E. This proves optimality for the stated finite model. It does not prove that the candidate list, durations or benefit estimates describe the factory perfectly.
See why two plausible rankings fail
A benefit-per-minute rule ranks C and D first, each at about 4.667 CU per minute. B follows at about 4.333, then E at four, A at about 3.889 and F at 3.75. Break the C/D tie by job letter and take each job that fits.
This procedure selects C, D and B. Their total is 270 minutes, 900 CU of cost and 1,220 CU of benefit. Ninety minutes remain, but every unselected job needs at least 120 minutes. The rule stops even though another combination would use the time more effectively.
Ranking by absolute benefit starts with A and E. Together they use 330 minutes and offer 1,300 CU of benefit. The thirty-minute gap cannot hold another listed job. This second plausible rule also misses the best feasible combination.
Selection method | Chosen jobs | Minutes used | Benefit, CU |
Benefit per minute, then fit | B, C, D | 270 | 1,220 |
Largest benefit, then fit | A, E | 330 | 1,300 |
Exact binary optimization | B, C, E | 360 | 1,540 |
The issue is indivisibility. A locally attractive job can consume the space needed by a better combination. Ratios remain useful descriptive information, but they do not certify a 0-1 optimum. Google's knapsack example frames the task as selecting the best feasible subset, rather than relying on a single item ranking.
Understand the dynamic programming calculation
Dynamic programming stores answers to smaller selection problems and reuses them. Define D(i,q) as the largest benefit available from the first i jobs within q units of time. In this example, all durations and the capacity are multiples of thirty minutes. We can therefore use thirty-minute units without rounding.
The job sizes become six, four, three, two, five and four units. Available capacity becomes twelve. D(0,q) is zero because no jobs have been considered. D(i,0) is zero because every job has a positive duration. For each later state, compare excluding the current job with including it when it fits.
D(i,q) = max[D(i−1,q), v(i) + D(i−1,q−w(i))]
The inclusion term is allowed only when q is at least w(i), the job's size in thirty-minute units. Both alternatives use row i−1, so the current job cannot be selected twice. The MIT knapsack notes explain this include-or-exclude recurrence and reconstruction of the chosen items.
Jobs considered so far | Best benefit within twelve units, CU |
A | 700 |
A, B | 1,220 |
A, B, C | 1,220 |
A, B, C, D | 1,500 |
A, B, C, D, E | 1,540 |
A, B, C, D, E, F | 1,540 |
When considering E, selecting it leaves seven units, or 210 minutes. Among A through D, the best set in that space is B plus C, worth 940 CU. Adding E's six hundred gives 1,540. Excluding E leaves the earlier 1,500-CU result. The inclusion branch wins.
The full table has seven rows, including the initial row, and thirteen capacity columns from zero through twelve. That is ninety-one cells. Store which branch wins at each state, then trace backward from the last cell. A maximum value alone is insufficient when the maintenance planner needs the actual job list.
Keep dynamic programming within its assumptions
The simple table just described tracks time only. Its final selection satisfies the base budget when checked separately, so it also certifies the base answer. Under a tighter budget, a time-only table can return a set that costs too much. Add a budget state or use the binary model with both constraints.
For n jobs and integer capacity C, the usual one-resource table requires work proportional to nC. MIT's complexity notes describe this as pseudopolynomial: runtime depends on the numeric capacity, not only the number of digits used to write it. Converting minutes to seconds can greatly enlarge the table without adding useful planning detail.
The thirty-minute conversion here is exact because every input is divisible by thirty. Rounding a forty-five-minute job down to one unit would create false capacity. If a coarser grid is required for another case, state how durations and capacity are rounded and independently recheck the selected jobs in original units.
A compressed one-row implementation needs another precaution. Update capacities downward for each job. An upward update may reuse a value created earlier in the same job's pass, allowing that job to appear twice. With only A available and capacity 360 minutes, the correct benefit is seven hundred; the faulty repeated-use calculation can return 1,400.

Reproduce the example with a short exact search
For six jobs, direct enumeration is transparent and easy to audit. This Python code checks both resource limits and retains every best set. It uses the standard library's Cartesian-product iterator, so no optimization package is required for this small demonstration.
from itertools import product
jobs = list("ABCDEF")
minutes = [180, 120, 90, 60, 150, 120]
cost = [500, 400, 300, 200, 350, 300]
benefit = [700, 520, 420, 280, 600, 450]
best, winners = -1, []
for x in product([0, 1], repeat=len(jobs)):
time_used = sum(t*b for t, b in zip(minutes, x))
spent = sum(c*b for c, b in zip(cost, x))
if time_used > 360 or spent > 1200:
continue
value = sum(v*b for v, b in zip(benefit, x))
picked = "".join(j for j, b in zip(jobs, x) if b)
if value > best:
best, winners = value, [picked]
elif value == best:
winners.append(picked)
print(best, winners) # 1540 ['BCE']
This code exhausts the entire six-job search space. Twenty jobs already produce 1,048,576 subsets, and the count doubles with each added binary job. Larger or richer models call for an appropriate solver or dynamic program. Keep the tiny exhaustive example as a check on the formulation, not as a claim that enumeration scales well.
Use the fractional model as a bound, not a work order
Temporarily allow every x(i) to take any value between zero and one. This linear relaxation includes all valid binary plans and additional fractional plans. Its highest benefit is therefore an upper bound on the binary maximum. The example's relaxation chooses B, C and D plus 0.6 of E.
The relaxed time is 120 + 90 + 60 + 0.6 × 150 = 360 minutes. Its cost is 1,110 CU, and its benefit is 520 + 420 + 280 + 0.6 × 600 = 1,580 CU. This is forty CU above the best whole-job result.
Taking sixty percent of E is not a valid package under the stated scope. Rounding E down leaves only 1,220 CU of benefit. Rounding it up requires 420 minutes and breaks the time limit. A fractional answer cannot be turned into a defensible work order by rounding each variable in isolation.
The relaxation was checked with SciPy linprog. The binary results were checked with SciPy milp, using integer variables bounded between zero and one. With a minimization interface, negate benefit coefficients to maximize the original benefit.
For a larger instance, report solver status and the remaining optimality gap if the run stops early. A feasible plan found before a time limit is still useful, but its status should not be upgraded to a proven optimum. Independently recompute its resource totals from the selected job IDs.
Tighten the spending limit and solve again
Suppose optional spending falls to 950 CU while time stays at 360 minutes. The former B/C/E plan costs 1,050 and is no longer feasible. Re-solving selects C, E and F. Their time is ninety plus 150 plus 120, exactly 360 minutes.
Their cost is three hundred plus 350 plus three hundred, exactly 950 CU. Their expected benefit is 420 + 600 + 450 = 1,470 CU. The budget change reduces the best modeled benefit by seventy CU compared with the original optimum.
Simply dropping B from the former plan would keep C and E at benefit 1,020. The new optimum instead replaces B with F. This illustrates why removing an expensive task without reconsidering all alternatives can waste both the budget and the shutdown opportunity.
The budget affects the selected combination, not merely the reported spending. Record whether each scenario changes the optional allowance or the total shutdown allowance. A revised total of 1,250 CU leaves 950 for optional work only if the earlier mandatory reserve remains three hundred.
Add dependencies and readiness restrictions explicitly
Consider a separate variant of the original budget: E may be selected only if D is also selected. Add x(E) ≤ x(D). The case assumes D's own benefit and E's incremental benefit remain additive, and their durations still represent separate work. The result must respect that changed technical relationship.
The earlier B/C/E set now fails because it includes E without D. The best feasible set becomes A, B and D, with time 360 minutes, cost 1,100 CU and benefit 1,500. Selection dependency is enforced, but the team must still put D before E in the execution sequence whenever both are chosen.
If two alternatives address the same problem and cannot both be used, an exclusion constraint can limit their sum to one. If a task lacks required parts or access, fix its selection variable to zero. Do not give it a low benefit and hope the optimizer happens to reject it.
For example, making C unavailable under the original other assumptions also gives A/B/D as the best set. ApparelDiary's critical spare-parts guide helps connect technical needs with stock readiness. The model needs usable, confirmed availability at the shutdown date, not an unverified expected receipt.
Price a time reserve without pretending it removes uncertainty
The base optimum fills every optional minute. If management requires a thirty-minute reserve, reduce optional capacity to 330 minutes and solve again. Two sets tie at benefit 1,400: A/C/D and B/D/E. Both use all 330 available minutes.
A/C/D costs one thousand CU; B/D/E costs 950. If lower cost is the agreed secondary objective, choose B/D/E. Report that a tie existed under the primary benefit objective. An unexplained solver tie-break should not become a claimed technical preference.
At 300 available minutes, the best set is C/D/E, worth 1,300 CU. At 330, the best value is 1,400; at 360 it is 1,540. These step changes describe this discrete task list. They do not justify assigning one constant monetary value to every extra minute.
The reserve sacrifices modeled benefit to leave room for execution uncertainty. It does not establish a probability of finishing on time. If durations vary materially or share common delays, test the selected set against realistic duration scenarios. A formal completion-probability target requires evidence and an uncertainty model beyond this deterministic knapsack.
Find the evidence threshold behind a close choice
The base result depends in part on E's estimated benefit of six hundred CU. Hold all other inputs fixed and let that benefit vary. The B/C/E set has benefit 940 plus E's value. Its nearest rival A/B/D remains at 1,500. Equating the two gives an E benefit of 560 CU.
At 560, both sets tie. At 550, B/C/E gives 1,490 and A/B/D wins with 1,500. At the original six hundred, B/C/E wins with 1,540. Checking every feasible subset confirms these conclusions for the stated values; comparing only two named sets would not, by itself, rule out a third competitor.
This threshold turns a vague request for better estimates into a focused question. Is there credible evidence that E's incremental benefit exceeds 560 CU over the chosen month? Review the specific failure mechanism and loss exposure behind E. If its plausible range crosses that figure, the choice is sensitive to that evidence.
Do not silently increase E's estimate to preserve a preferred plan. Show the range and the alternative it implies. The team may choose a conservative appraisal, gather another condition reading or use a documented secondary preference. Each approach should remain visible in the decision record rather than being hidden in an unexplained score adjustment.
The threshold also defines the scope of the sensitivity check. It assumes B, C and the competing jobs keep their original values and that all resource limits stay fixed. If several benefits change together, re-evaluate the complete sets with those joint changes. Independent one-at-a-time thresholds do not describe every combined scenario.
Finally, distinguish benefit uncertainty from poor job definition. A task with unclear scope may have uncertain duration, cost and effect at once. Clarifying that scope can be more useful than calculating more decimal places for its benefit. The selected work should have a clear completion test so the later review can establish what was actually delivered.
Check whether the selection can become a real shutdown plan
A sum of durations is sufficient here because one crew works serially, all jobs are ready at the start, and there are no additional timing restrictions. Real work can involve parallel specialists, shared isolation windows or delayed access. A set that fits in aggregate hours may still have no feasible detailed schedule.
Convert the chosen job set into start times, resource assignments and release checks. Confirm which tasks may overlap and which must follow earlier work. ApparelDiary's production calendar calculations explain why elapsed time and resource time need explicit definitions. Keep the shutdown model's clock equally clear.
Benefits also need a set-level review. Two repairs may prevent the same stoppage, so adding both standalone loss estimates would double count it. Conversely, one job may have value only when a companion task is complete. Use revised package values or appropriate interaction variables when that relationship changes the decision.
Record the estimated benefit range, not just a single number. The forty-CU margin between B/C/E and A/B/D is small in this teaching case. If the underlying estimates can readily move by that amount, show both alternatives to the reviewer with their technical differences. A precise optimum is conditional on its inputs.
After the shutdown, retain actual durations, spend, completed scope and outstanding defects. Compare forecast benefits with subsequent evidence over the defined horizon, allowing for changes in production duty. One quiet month does not prove every avoided failure estimate. The purpose of feedback is to improve future inputs and task design.
Frequently asked questions
Must all available time be used?
No. The constraint is an upper bound. An optimal set may leave time unused when no additional whole job fits or when another resource binds. Filling minutes is not the objective unless the business explicitly chooses that objective.
Is the highest benefit-per-minute job always selected?
No. In this example D ties for the best ratio but is absent from the base optimum. Its removal allows the more valuable B/C/E combination. Ratios describe individual jobs; the model compares complete sets.
Can one job be split across two shutdowns?
Only if its technical scope permits that split and the model represents it. The present binary package must be completed in one shutdown. Splitting it changes setup time, remaining work and when its benefit becomes available.
Conclusion
Maintenance knapsack optimization makes a limited shutdown's selection trade-off explicit. For the stated example, B, C and E provide the largest expected benefit of 1,540 CU within 360 minutes and the 1,200-CU optional budget. Greedy rankings miss that combination.
Keep mandatory work outside the optional competition, verify readiness, and define benefit without overlap. Use exact methods appropriate to the task list, preserve binary choices and re-solve after material changes. Then test whether the selected jobs can be executed within the real shutdown's resource and timing conditions.
Shutdown selection relies on reliability data, so see preventive versus predictive maintenance and MTBF and MTTR calculation.
References
1. Google OR-Tools: The Knapsack Problem.
2. Google OR-Tools: Packing Problem Definitions.
3. JuMP: The Knapsack Problem Example.
4. MIT 6.006: Subset Sum Variants and the 0-1 Knapsack Recurrence.
5. MIT 6.006: Knapsack and Pseudopolynomial Complexity.
6. US Department of Energy: Operations and Maintenance Best Practices, Release 3.0.




Discussion0
Loading the discussion…