Understanding Transport Constraints and Resource Modeling

1. From Idealized Transport to Realistic Constraints

In introductory scheduling models, transportation is often either ignored or heavily simplified. As your work requires a high degree of academic rigor, it's essential to understand the different levels of modeling transport and why a detailed approach is necessary.

The best way to see this is to compare different problem definitions. A research paper by Berterotti`ere et al. offers a clear way to categorize these problems.

As the table illustrates, we can distinguish between two main ways of considering transport:

1. FJSP with Transportation Times (Time Lags): This approach adds a fixed or machine-dependent travel time between consecutive operations of a job. For example, after an operation on Machine A finishes, a delay of $\Delta t$ is added before the next operation can start on Machine B. The critical assumption here is that a transportation resource is always available the instant it's needed. This is often unrealistic, as it implies an infinite number of vehicles, which is costly and would lead to congestion.

2. FJSP with Transportation Resources (FJSPT): This is the more realistic and complex model that we will focus on. It explicitly models a finite fleet of vehicles (e.g., AGVs). This means transportation itself becomes a scheduled activity. This model decomposes the problem into several interdependent subproblems, including:

   • Machine Assignment: Assigning a production operation to an eligible machine.
   • Operation Sequencing: Sequencing the operations assigned to each machine.
   • Vehicle Assignment: Assigning a transport task to an available vehicle.
   • Vehicle Routing/Scheduling: Sequencing the transport tasks for each vehicle.

By modeling transport resources explicitly, we acknowledge that vehicles are a bottleneck and their availability directly impacts the production schedule.

2. Defining Transport Operations and Resources

To model the FJSPT, we need to formalize the components of the transportation system. Let's define the key concepts, drawing from the formal problem description found in scheduling literature.

A transport operation is initiated when a job finishes a production operation $O_{i,j}$ (operation $j$ of job $i$) on machine $M_a$ and needs to move to machine $M_b$ for the next production operation, $O_{i,j+1}$.

This process involves two key phases for the vehicle:

• Empty Travel: The vehicle, currently located where it finished its last task (e.g., at machine $M_c$), travels empty to the pickup location, machine $M_a$. The time for this depends on the distance between $M_c$ and $M_a$.
• Loaded Travel: The vehicle picks up the job at machine $M_a$ and transports it loaded to the drop-off location, machine $M_b$. The time for this depends on the distance between $M_a$ and $M_b$.

A key assumption often made in this context, which is quite realistic, is that travel times satisfy the triangular inequality: the time to travel from A to B is always less than or equal to the time to travel from A to C and then from C to B.

This explicit handling of transport introduces significant dependencies. A job can't start processing on a machine until it physically arrives, and its arrival time depends on:

1. When its previous operation was completed.
2. When a vehicle was assigned to transport it.
3. The vehicle's location prior to the task (determining empty travel time).
4. The travel time from the pickup to the drop-off machine (loaded travel time).

3. Key Parameters and Variables for Modeling Transport

Now that we have defined the concepts, let's see how they are translated into a mathematical model. While the full MILP integration is the topic of our next lesson, we can already define the necessary building blocks: the parameters and decision variables.

Based on your background in mathematical analysis, you'll recognize this as the first step in formulating any optimization problem. We'll again refer to the model by Homayouni and Fontes as it lays out these components very clearly.

Key Parameters (Inputs to the model)

• $A$: The number of available vehicles in the fleet.
• ${\tau }_{kl}$: The empty travel time for a vehicle to move from the location of task $k$'s drop-off to the location of task $l$'s pick-up.
• ${\theta }_l$: The loaded travel time required for transport task $l$. This is the time to move the job from its origin machine to its destination machine.

Key Decision Variables (Outputs of the model)

• $r_l$: A continuous variable representing the arrival time of the job for operation $l$ at its designated machine. This is a critical variable connecting the transport and production schedules.
• $x_{kl}$: A binary variable that equals 1 if transport task $l$ is performed by the same vehicle immediately after transport task $k$. This variable establishes the sequence, or route, for each vehicle.
• $y_l$: A binary variable that equals 1 if transport task $l$ is the first task performed by any vehicle.

Using these variables, we can formulate constraints that govern the transport system. For example:

• Vehicle Capacity: The number of vehicle routes (i.e., the number of tasks designated as a "first task") cannot exceed the total number of available vehicles ($A$).
  ${\sum }_l{y}_l\le A$
• Job Arrival Time: A production operation $l$ (with predecessor ${\mu }_l$) cannot start before the job arrives. The arrival time $r_l$ must be greater than or equal to the completion time of the previous operation $c_{{\mu }_l}$ plus the loaded travel time ${\theta }_l$.
  $r_l\ge c_{{\mu }_l}+{\theta }_l$
• Vehicle Continuity: If a vehicle performs task $l$ right after task $k$, its arrival at the destination for task $l$ depends on when it arrived at its destination for task $k$ ($r_k$), plus the empty travel time (${\tau }_{kl}$) and loaded travel time (${\theta }_l$) for the new task. This creates a "no-overlap" constraint for vehicles.
  $r_l\ge r_k-(\text{loaded time for k})+{\tau }_{kl}+{\theta }_l$
  (Note: This is a simplified representation of constraint (14) in the paper, which uses the "big-M" method to activate it only when $x_{kl}=1$.)

Conclusion

In this lesson, you have learned to define and conceptualize transport constraints in a flexible job shop environment. This is a significant step up from simplified models and is essential for creating scheduling models that reflect real-world logistics.

Key Takeaways:

• Modeling transportation resources (like a finite fleet of AGVs) is more realistic than using simple transportation times (time lags), as it accounts for vehicles being a limited, shared resource.
• This introduces new scheduling decisions: vehicle assignment (which vehicle takes which job) and vehicle routing (the sequence of tasks for each vehicle).
• The total transport time for a single job movement consists of two parts: the empty travel of the vehicle to the pickup location and the loaded travel to the drop-off location.
• We can begin to model these constraints mathematically by defining specific parameters (travel times, fleet size) and decision variables (vehicle sequences, job arrival times).

Preview of the Next Lesson:

We have now defined all the necessary components for both sequence-dependent setups and transportation. In our next lesson, we will put everything together and focus on how to integrate transport time and resource constraints into scheduling models. We will explore how to extend the disjunctive graph to include vehicle resources and how to write the complete MILP constraints that simultaneously solve for the production and transportation schedules.