PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimizing the makespan in job shop scheduling under conflict graph constraints

Nour Elhouda Tellache, Abdenour Azerine

arXiv:2609.04161v1cs.DMmath.OC

TL;DR

The paper studies makespan minimization in job shop scheduling when conflict-graph-adjacent jobs cannot run simultaneously. It develops complexity results, formulations, lower bounds, and a genetic algorithm; computational evaluation reports lower average RPD at higher conflict density in most tested instance sets, with Taillard instances as an exception.

  • Problem

    The paper studies how to minimize makespan in job shop scheduling when jobs joined by an edge in a conflict graph cannot run simultaneously on different machines.

    Source: §1 · p. 1

  • Method

    The paper establishes a resource-constrained job shop equivalence, develops mixed-integer formulations and lower bounds, and proposes a genetic algorithm.

    Source: §4.1 · p. 7, §5.2 · pp. 10–11, §8 · p. 29

  • Results

    Increasing conflict density from p=0.2 to p=0.8 reduces average RPD across the three approaches except on Taillard instances, where the highest RPD occurs at p=0.5.

    Source: §7.6 · p. 25

  • Takeaways & Limitations

    The analysis gives a polynomially solvable two-machine restriction alongside NP-hardness for the general two-machine problem.

    Source: §8 · p. 29

    The complexity of J2|rest111, pij=1|Cmax remains open.

    Source: §3 · p. 7

Abstract

from arXiv · show

We study the job shop scheduling problem with a conflict graph (JSC), in which adjacent jobs in the conflict graph cannot be processed simultaneously on different machines, with the objective of minimizing the makespan. The problem models settings where jobs share additional resources while retaining their individual machine routings. We first investigate its computational complexity and establish a polynomial equivalence between JSC and a variant of the resource-constrained job shop problem with unit-capacity resources. Although the general problem on two machines is NP-hard, we identify a polynomially solvable special case. For the general problem, we develop precedence-based and time-indexed mixed-integer linear formulations, along with lower bounds on the makespan. We also propose a genetic algorithm using permutation-with-repetition encoding and active, non-delay, and hybrid schedule evaluation procedures. Computational experiments on instances derived from the Lawrence and Taillard benchmarks, as well as randomly generated generalized job shop instances, are conducted to evaluate the performance of the proposed formulations, lower bounds, and genetic algorithm.

1. Introduction

The paper introduces job shop scheduling with conflict constraints, where graph-adjacent jobs cannot run simultaneously on different machines, and seeks to minimize makespan. It situates this model among resource-constrained job shop problems.

1. Introduction

  • The model addresses settings where jobs cannot run concurrently because they share additional resources, while their machine routings remain individual.The paper relates job-level conflicts to resource-constrained job shop scheduling, where conflicts arise when resource requirements exceed capacity.Source: §1 · pp. 1–2
  • JSC schedules ordered job operations on dedicated machines while forbidding simultaneous processing of jobs joined by an edge in a simple undirected conflict graph.Each operation has a specified machine and processing time; jobs retain their individual machine routings.Source: §1 · p. 1
  • The objective is to minimize makespan, the maximum completion time, subject to machine, job, and conflict constraints.A machine handles at most one operation at a time, and each job is processed on at most one machine at a time.Source: §1 · pp. 1–2
  • The paper characterizes resource-constrained scheduling variants by resource types, availabilities, and requirements, including cases where a job’s operations share resource requirements.It denotes the latter special case using restλσδ and identifies it as a subproblem of the more general resλσδ class.Source: §1 · p. 2

2. Literature review

The reviewed literature establishes extensive complexity results for open shop and flow shop scheduling with conflict graphs, while covering tractable cases and solution approaches alongside hard cases.

2. Literature review

  • Open shop with conflict graphs is strongly NP-hard for at least two machines, but polynomial cases include unit-time operations on selected graph classes and preemptive two-machine settings.For two machines, the surveyed work also reports heuristic approaches and lower bounds for the general case.Source: §2 · pp. 2–3
  • A hybrid genetic algorithm with mathematical models and lower bounds optimally solved 93.49% of surveyed open-shop instances, with 0.475% average deviation from best-known lower bounds.It outperformed the two-phase heuristic approach.Source: §2 · p. 3
  • Flow shop with conflict graphs is harder than open shop: two-machine cases are strongly NP-hard, while unit-time single-operation jobs admit an O(n^2.5) solution.For unit-time operations, the surveyed work connects complexity to Minimum Path Cover and reports heuristic approaches and lower bounds for general machine counts.Source: §2 · p. 3
  • For two-machine FSC, permutation schedules are not dominant, though a special case has an optimal permutation schedule; the problem remains NP-hard on complements of trees, even with preemption,.Source: §2 · p. 3

3. Complexity analysis

The complexity analysis establishes a polynomial equivalence between JSC and a unit-resource job shop variant, proves hardness for the general two-machine case, and identifies a polynomially solvable restriction. Its schedule constructions use job-class counts to characterize optimal makespans and unavoidable idle time.

3. Complexity analysis

  • The general two-machine JSC problem is NP-hard, while the complexity of J2|rest111, pij=1|Cmax remains open.The cited hardness for the broader resource-constrained variant does not directly extend when operations within each job have identical resource requirements.Source: §3 · pp. 3, 4, 7
  • JSC is polynomially equivalent to J|rest.11|Cmax by mapping each conflict edge to a unit-capacity resource shared by its two endpoint jobs, and mapping shared resources back to conflict edges.In the resulting problems, two jobs can run simultaneously exactly when they do not share a resource.Source: §3 · p. 4
  • Two-machine unit-time JSC with at most two operations per job is polynomially solvable when the conflict graph is a complement of a complete split graph.The equivalent resource-constrained restriction J2|rest111, pij=1, mj≤2|Cmax is also polynomially solvable.Source: §3 · pp. 4, 6
  • For Case 1, comparing the S and C job-class counts yields schedules with no idle time across balanced and strictly smaller C-class subcases, including cases with empty sets.The construction pairs C1 with S2 and C2 with S1, then schedules remaining operations; the figures illustrate the non-empty, empty-set, and strict-inequality variants.Source: §3 · pp. 4–5, Figure 1 · p. 4, Figure 2 · p. 5
  • For Case 2, equal total class counts permit a no-idle schedule; when C1+C2 exceeds S1+S2, the unavoidable idle time on each machine is C1+C2−S1−S2.The case with smaller total C-class count is also constructed by pairing operations, and Case 3 follows by symmetry.Source: §3 · p. 6, Figure 4 · p. 6, Figure 5 · p. 6
  • When both C1 and C2 exceed their corresponding S-class counts, the remaining conflicting C jobs occupy disjoint intervals, producing C1+C2−S1−S2 unavoidable idle time on each machine.The schedule pairs S2 jobs with C1 jobs and S1 jobs with C2 jobs before scheduling the remaining C jobs separately.Source: §3 · p. 6

4. Mathematical formulations

The section presents four MILP formulations for JSC that incorporate conflict constraints between jobs. It also introduces a fast heuristic to warm-start the solver and provide an upper bound within the time limit.

4.1. Precedence relationship-based formulation.

  • The precedence-based F1 formulation minimizes makespan while enforcing job precedence, machine sequencing, and nonoverlap between operations of conflicting jobs.Its binary variables encode operation order on a shared machine or between conflicting jobs on different machines.Source: §4.1 · p. 7
  • F2 replaces paired ordering constraints with symmetric binary variables and symmetry equalities for machine and conflict disjunctions.The remaining F1 constraints are unchanged.Source: §4.1 · pp. 7–8

4.2. Time-indexed formulation.

  • The time-indexed F3 formulation uses a binary variable for each operation start time, with a bound on job completion times.Its constraints encode operation starts, job precedence, machine capacity, conflict nonoverlap, and makespan.Source: §4.2 · p. 8
  • Replacing F3's conflict constraints with an equivalent conflict-degree formulation reduces the constraint count from O(|E|T) to O(|V|T).The reformulation uses each job's conflict degree and its neighbors in the conflict graph.Source: §4.2 · p. 9

4.3. Warm start.

  • For large instances, the mathematical formulations may fail to find a feasible solution within the time limit, motivating a fast heuristic warm start.The warm start is intended to help the solver produce an upper bound within that limit.Source: §4.3 · p. 9
  • The warm-start heuristic selects among each job's next unscheduled operations by earliest start time, breaking ties using remaining-workload and conflict information.The priority metric reflects both the current job's workload and the workload of conflicting jobs.Source: §4.3 · p. 9
  • After selecting an operation, the heuristic postpones earlier-starting operations that conflict with it until its completion time.This prevents simultaneous execution of operations that conflict through the same job or through conflicting jobs.Source: §4.3 · p. 10
  • Eight additional job-priority rules use operation-processing-time and job-length measures to select operations for the warm-start schedule.The rules include ordering by total processing time, maximum or minimum operation time, number of operations, and mean operation time.Source: §4.3 · p. 10

5. Lower bounds

The paper extends three classes of makespan lower bounds to the general JSC problem, using them to assess solution quality and stop the genetic algorithms. The bounds range from classical job-shop relaxations to graph-based and solver-derived bounds.

5. Lower bounds

  • Three classes of makespan lower bounds are adapted from the open-shop conflict-graph problem and extended to JSC.They are used in genetic-algorithm stopping criteria and to benchmark solution quality of the algorithms and mathematical formulations.Source: §5 · p. 10

5.1. Conflict constraint relaxation-based lower bounds.

  • Relaxing inter-job conflicts yields the basic job-shop problem, so its bounds apply; the classical bound uses maximum machine load and total job processing time.A bound can also sum processing times over a set of mutually conflicting jobs or operations, which must run in disjoint time intervals.Source: §5.1 · p. 10

5.2. Weighted agreement graph-based lower bound.

  • The maximum-weight independent set in the weighted agreement graph gives a valid makespan lower bound, but finding it is NP-hard; GWMIN and GWMIN2 approximate it as LB2 and LB3.The agreement graph complements the conflict graph, with job processing times as vertex weights.Source: §5.2 · p. 10
  • Solving formulations F1–F4 under a fixed time limit yields bounds LB4–LB7, which are at least as tight as their linear-relaxation bounds.LB4, LB5, LB6, and LB7 correspond respectively to F1, F2, F3, and F4.Source: §5.2 · p. 11

6. Genetic algorithms

The genetic algorithm evolves job-sequence chromosomes and evaluates them by decoding into feasible schedules. Its design combines repeated-job encoding, schedule-building procedures, population initialization, genetic operators, and a repair step for infeasible offspring.

6. Genetic algorithms

  • The GA evolves an elite set within a population, repeatedly selecting parents, applying probabilistic crossover and mutation, and returning the best schedule found.The process begins with a population of size Np and selects Ne elite chromosomes; it repeats until a stopping criterion is met.Source: §6 · p. 11

6.1. Encoding and decoding.

  • Repeated-job permutations encode each operation in job order, preserving within-job precedence and chromosome feasibility throughout the evolutionary process.The i-th occurrence of a job index represents its i-th operation; decoding schedules the next unscheduled operation of that job.Source: §6.1 · pp. 11–12
  • Chromosomes decode into active or non-delay schedules, with makespan used as fitness; the active-schedule procedure follows Giffler and Thompson’s mechanism.Every optimal schedule for a regular measure such as makespan is active, but not every optimum is non-delay; non-delay schedules restrict the search space.Source: §6.1 · p. 12

6.2. Initial population generation.

  • Initial populations can be random or seeded with unique chromosomes built by sorting operations using processing time, conflict degree, or agreement-degree ratios.The criteria include increasing and decreasing orders of processing time, conflict degree, conflict-degree-to-processing-time ratio, and agreement-degree-to-processing-time ratio.Source: §6.2 · p. 13

6.3. Selection, crossover, and mutation.

  • Parent selection uses n-size tournaments, and the GA uses one-point, two-point, or mask-based crossover plus swap or move mutation.Mask-based crossover can violate job-occurrence counts, so its offspring require repair before decoding and fitness evaluation.Source: §6.3 · pp. 13–14, §6.4 · p. 14

6.4. Post-processing (repair) procedure.

  • Repair replaces surplus job-index occurrences with missing ones until each job appears as often as its operation count, preserving unaffected gene order as much as possible.Replacements proceed sequentially from left to right to limit disruption of inherited genetic structures.Source: §6.4 · p. 14

7. Computational experiments

Experiments assess formulations on Taillard- and Lawrence-derived benchmarks and randomly generated generalized job-shop instances. Among the formulations, F2 performs best overall, while model size and computational difficulty rise with instance size and conflict density.

7. Computational experiments

  • The experiments use Taillard- and Lawrence-derived benchmark sets and randomly generated generalized job-shop instances, totaling 240, 120, and 270 instances, respectively.Conflict graphs for the two benchmark sets use edge probabilities 0.2, 0.5, and 0.8; five random instances were generated for each generalized-instance parameter combination.Source: §7 · pp. 14–15

7.1. Performance of the mathematical models.

  • Among time-indexed formulations, F4 performs better on small, low-density instances, while F3 performs better as size and conflict density increase.The pairwise conflict constraints in F3 provide a stronger formulation than F4’s aggregated degree-based constraints, particularly for larger and denser instances.Source: §7.1 · pp. 15–16
  • F2 outperforms F1 on most instances, indicating that its additional equality constraints strengthen the formulation despite adding symmetric variables.Source: §7.1 · p. 16
  • Larger instances and denser conflict graphs generally produce larger, harder models, while wider processing-time ranges particularly affect time-indexed formulations as their discretized horizon grows.Source: §7.1 · p. 16
  • F2 solves 49 of 90 instances to optimality with a 0.276% average gap, the best overall performance; precedence-based F1 and F2 outperform time-indexed F3 and F4.The reported comparison is in Table 1; the precedence-based advantage is especially clear for instances with larger processing-time intervals.Source: §7.1 · p. 15, Table 1 · p. 16

7.2. Performance of the lower bounds.

Lower-bound quality depends strongly on conflict-graph density: LB1 is competitive on sparse graphs, while LB2 and LB3 are tighter on medium- and high-density graphs. LB2 and LB3 perform similarly overall, and MILP-based bounds could not be retrieved for many medium and large instances because of memory limits.

7.2. Performance of the lower bounds.

  • For medium and large instances, memory exhaustion often prevented retrieval of LP-relaxation bounds, so MILP-based lower bounds are omitted from the reported results.The experiments also encountered out-of-memory errors under the 32 GiB limit for some larger instances.Source: §7.2 · p. 16
  • LB1 is competitive on sparse graphs but degrades as density rises, whereas LB2 and LB3 provide tighter bounds at medium and high densities.For p = 0.5 and p = 0.8, LB2 and LB3 average deviations from the best lower bound are generally below 1%.Source: §7.2 · pp. 17–18, Table 2 · p. 17, Table 3 · p. 17
  • LB2 and LB3 have similar overall performance; LB3 has a slight advantage on the largest and densest instances, with best bounds on 72.31% and 75.09% of instances, respectively.Their average deviations from the best lower bound are 4.95% for LB2 and 5.30% for LB3; both use a greedy independent-set procedure but different vertex-selection rules.Source: §7.2 · pp. 18–19

7.3. Sensitivity analysis of core genetic algorithm operators.

The operator comparisons favor non-delay evaluation for efficiency, with quality comparable to active evaluation on benchmark-derived instances and better on generalized instances. Crossover differences are modest, while selected configurations usually favor non-delay evaluation and two-point crossover.

7.3.1. Impact of the evaluation strategy.

  • Non-delay evaluation matches active evaluation without significant quality differences on Lawrence and Taillard instances while reducing runtime; on generalized instances it improves quality by 2.22% and reduces runtime by 45–55%.Non-delay schedules are a subset of active schedules and may exclude optimal solutions, although every optimal schedule for makespan is active.Source: §7.3.1 · pp. 19–20, Table 6 · p. 19

7.3.2. Impact of crossover operators.

  • Mask crossover has the lowest mean objective on Lawrence instances, while two-point crossover does so on Taillard and generalized instances; differences are modest, and swap and insertion mutation perform comparably.No statistically significant difference was observed between the two mutation operators.Source: §7.3.2 · p. 20, §7.3.3 · p. 20, Table 7 · p. 20

7.3.3. Selection of GA configuration.

  • Selected configurations use non-delay evaluation in eight of nine instance-set–density combinations and two-point crossover in six, with mask crossover selected for the remaining Lawrence configurations.Active evaluation is selected only once.Source: §7.3.3 · p. 21, Table 8 · p. 21

7.4. Impact of hybrid evaluation strategy on GA performance.

The hybrid strategy probabilistically combines active and non-delay schedule evaluation to expand the schedules explored beyond non-delay alone. A 0.5 probability of active evaluation is a competitive, often superior compromise, particularly for generalized job shop instances.

7.4. Impact of hybrid evaluation strategy on GA performance.

  • The hybrid strategy probabilistically evaluates offspring using active schedules, with p = 0 corresponding to non-delay evaluation and p = 1 to active evaluation alone.It is considered because restricting the search to non-delay schedules may prevent reaching optimal schedules; hybridization expands the schedules explored by the GA.Source: §7.4 · pp. 21–22
  • A 0.5 active-evaluation probability provides a competitive and often superior compromise, and consistently performs best on generalized job shop instances.Heavier reliance on active evaluation generally leads to poorer solution quality; differences between low and moderate probabilities are generally small for Lawrence- and Taillard-derived instances.Source: Table 9 · p. 21, §7.4 · p. 22

7.5. Tuning the numerical GA parameters.

The parameter tuning selects a population size of 400, mutation probability of 0.5, and crossover probability of 0.9 for the final GA configuration. The observed numerical trends are generally modest or not statistically significant.

7.5. Tuning the numerical GA parameters.

  • Population size 400 yields the lowest average objective value across all three instance sets, but the overall effect is not statistically significant (p-value = 0.1042) and observed effect sizes are small.The tuning selects Np = 400 for the final configuration.Source: Table 10 · p. 22, §7.5 · pp. 23–24
  • Mutation probability 0.5 consistently gives the best average performance, although its practical impact is limited by consistently very small effect sizes.Statistically significant differences occur only for selected instance-set–density combinations; pm = 0.5 is selected for the final configuration.Source: Table 11 · p. 22, §7.5 · p. 24
  • Crossover probability 0.9 yields the lowest average objective value in each instance set, but differences are small and not statistically significant (p-value > 0.05).The final configuration uses pc = 0.9.Source: Table 12 · p. 22, §7.5 · p. 24

7.6. Final computational evaluation.

The final evaluation finds that the genetic algorithms generally outperform the constructive heuristic, while heuristic seeding offers no systematic advantage over random initialization. Solution quality and variability also depend on conflict density and benchmark family.

7.6. Final computational evaluation.

  • RPD, standard deviation, and CPU time are reported for H, randomly initialized GA, and heuristic-seeded GAh.RPD is measured from the best available lower bound; GAh seeds its initial population with heuristic chromosomes and fills the remainder randomly.Source: §7.6 · p. 24
  • The genetic algorithms generally outperform H across Lawrence, Taillard, and generalized job shop instances.The reported average RPDs decrease for each benchmark family and density, though the improvement is more modest on generalized instances.Source: §7.6 · pp. 24–25, Table 14 · p. 25, Table 15 · p. 26
  • The Friedman and adjusted Wilcoxon analyses find significant GA and GAh improvements over H except on generalized instances at p = 0.2.Significant improvements are reported for Lawrence and Taillard at every density and generalized instances at p = 0.5 and p = 0.8.Source: §7.6 · p. 25, Table 17 · p. 27
  • Increasing conflict density generally reduces average RPD, except Taillard instances peak at p = 0.5.The paper attributes the trend partly to tighter lower bounds and a more restricted feasible search space at higher densities.Source: §7.6 · p. 25
  • GA and GAh have nearly identical average solution quality and computational times, with no statistically significant difference across benchmark–density combinations.The best RPD alternates between variants, and pairwise Wilcoxon tests have p-values above 0.05 throughout.Source: §7.6 · p. 26, Table 17 · p. 27
  • The GA variants produce less variable solution quality than H; at p = 0.8, standard deviations are at most 2.53%.Variability generally decreases with conflict density, though this pattern is not systematic for Taillard instances.Source: §7.6 · pp. 26–27

7.6.1. Solution quality distribution.

  • At p = 0.2, H has a higher median and wider interquartile range than GA and GAh; at p = 0.8, all methods cluster near zero.Figure 6 shows RPD distributions by method and density across benchmarks; outliers at low and medium densities typically involve the largest instances.Source: §7.6.1 · p. 28, Figure 6 · p. 28
  • Generalized instances have the highest average RPD and Lawrence the lowest; H exceeds both GA variants at p = 0.2 and p = 0.5.At p = 0.8, the three methods' bars are nearly equal; standard-error bars are wider for H.Source: §7.6.2 · p. 28, Figure 7 · p. 28

8. Conclusions

The paper establishes complexity results, formulations, lower bounds, and a genetic algorithm for job shop scheduling with graph-represented conflict constraints.

8. Conclusions

  • The paper studies graph-constrained job shop scheduling, establishing complexity results and presenting formulations, lower bounds, and a genetic algorithm.It proves NP-hardness for two machines and a polynomially solvable case for two machines, unit-time operations, and jobs with at most two operations under complements of complete split graphs; future directions include exact and online methods.Source: §8 · p. 29
Loading 2609.04161v1…