FJSP modeling: Handling conflicts between machine chains and job precedence constraints

[JayYang168]

Hi Timefold team,

I am modeling a Flexible Job Shop Scheduling Problem (FJSP) using the chained planning variable approach.

Current setup:

• Each operation is assigned to a machine.
• Machine sequencing is modeled using a chained variable (previousJob).
• Start/end times are computed via a shadow variable based on the machine chain.
• Job precedence (operation order within the same job) is modeled as a hard constraint:
  start(op_j) >= end(op_i)

Problem:
This creates a structural conflict:

• The machine chain determines time propagation.
• Precedence constraints form a DAG that is not part of the chain.

Observed behavior:

1. Many intermediate solutions violate precedence constraints.
2. The solver sometimes struggles to recover feasibility.
3. In some cases, jobs remain unassigned because satisfying both constraints is difficult.
4. Since startTime is not a planning variable, the solver can only indirectly fix violations via machine/sequence moves.

Questions:

1. Is it the recommended approach in Timefold to model precedence purely as constraints (not part of the chain)?
2. Are there best practices to improve feasibility in this setup (e.g. Construction Heuristics, soft constraints to guide ordering, etc.)?
3. Should time flexibility (idle gaps) be explicitly modeled to help resolve precedence violations?
4. Is there any official example for FJSP (machine chains + precedence constraints together)?
5. If possible, could you provide a minimal example (code snippet or reference) demonstrating the recommended modeling pattern for handling both machine chains and precedence constraints?

Any guidance or recommended modeling patterns would be greatly appreciated.

Thanks!

[Christopher-Chianelli]

1. The recommended approach is to use declarative shadow variables, which will calculate your start and end times in topological order based on declared dependencies; see

   timefold-solver/core/src/test/java/ai/timefold/solver/core/testdomain/shadow/dependency/TestdataDependencyValue.java

   Lines 76 to 96 in a5e9920

   	@ShadowSources({ "dependencies[].endTime", "previousValue.endTime", "entity" })
   	public LocalDateTime calculateStartTime() {
   	LocalDateTime readyTime;
   	if (previousValue != null) {
   	readyTime = previousValue.endTime;
   	} else if (entity != null) {
   	readyTime = entity.startTime;
   	} else {
   	return null;
   	}
   	if (dependencies != null) {
   	for (var dependency : dependencies) {
   	if (dependency.endTime == null) {
   	return null;
   	}
   	readyTime = ObjectUtils.max(readyTime, dependency.endTime);
   	}
   	}
   	return readyTime;
   	}

2. Unfortunately, in Flexible Job Shop Scheduling, it is very hard to generate neighbouring feasible solution from an initial feasible solution since just reordering something violates the precedence constraints. The recommended approach is to use custom moves that generate feasible schedules either using custom move iterators (https://docs.timefold.ai/timefold-solver/latest/optimization-algorithms/move-selector-reference#customMovesIntroduction) or the currently in beta neighbourhoods feature (https://docs.timefold.ai/timefold-solver/latest/optimization-algorithms/neighborhoods).
3. With declarative shadow variables, as long as an operation is processed after its dependencies, no precedence violation occurs. It up to you if you want to have idle gaps or not; I would not explcitly model it, but it include it inside the start time calculation (but it up to you).
4. The closest thing to an official example for FJSP (machine chain + precedence constraints) is this testdata package (https://github.com/TimefoldAI/timefold-solver/tree/main/core/src/test/java/ai/timefold/solver/core/testdomain/shadow/dependency); there is an official quickstart for project job scheduling (https://github.com/TimefoldAI/timefold-quickstarts/tree/stable/java/project-job-scheduling) but that doesn't have machine chain IIRC (instead, operations are automatically ordered based on their dependencies and when their resources will be avaiable).
5. See my answers to 1 and 4.

[JayYang168]

Thanks for the guidance.  I built a test case referencing this https://github.com/TimefoldAI/timefold-solver/blob/a5e99204f267756f83da0fbcfce790342069d9d6/core/src/test/java/ai/timefold/solver/core/testdomain/shadow/dependency/TestdataDependencyValue.java#L76-L96.The setup involves 300 orders, each with 3 tasks, processed on a single machine. I configured the FIRST_FIT construction heuristic strategy, but it takes nearly 7 minutes to schedule all tasks. Why is the heuristic strategy so slow in this scenario? Are there any methods to speed it up? I would appreciate your insights. Best regards. yy ***@***.*** 原始邮件 发件人：Christopher Chianelli ***@***.***> 发件时间：2026年3月20日 12:14 收件人：TimefoldAI/timefold-solver ***@***.***> 抄送：JayYang168 ***@***.***>, Author ***@***.***> 主题：Re: [TimefoldAI/timefold-solver] FJSP modeling: Handling conflictsbetween machine chains and job precedence constraints (Discussion #2198) The recommended approach is to use declarative shadow variables, which will calculate your start and end times in topological order based on declared dependencies; see https://github.com/TimefoldAI/timefold-solver/blob/a5e99204f267756f83da0fbcfce790342069d9d6/core/src/test/java/ai/timefold/solver/core/testdomain/shadow/dependency/TestdataDependencyValue.java#L76-L96 Unfortunately, in Flexible Job Shop Scheduling, it is very hard to generate neighbouring feasible solution from an initial feasible solution since just reordering something violates the precedence constraints. The recommended approach is to use custom moves that generate feasible schedules either using custom move iterators (https://docs.timefold.ai/timefold-solver/latest/optimization-algorithms/move-selector-reference#customMovesIntroduction) or the beta neighbourhoods feature (https://docs.timefold.ai/timefold-solver/latest/optimization-algorithms/neighborhoods). With declarative shadow variables, as long as an operation is processed after its dependencies, no precedence violation occurs. It up to you if you want to have idle gaps or not; I would not explcitly model it, but it include it inside the start time calculation (but it up to you). The closest thing to an official example for FJSP (machine chain + precedence constraints) is this testdata package (https://github.com/TimefoldAI/timefold-solver/tree/main/core/src/test/java/ai/timefold/solver/core/testdomain/shadow/dependency); there is an official quickstart for project job scheduling (https://github.com/TimefoldAI/timefold-quickstarts/tree/stable/java/project-job-scheduling) but that doesn't have machine chain IIRC (instead, operations are automatically ordered based on their dependencies and when their resources will be avaiable). See my answers to 1 and 4. — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you authored the thread.