Practical stuff

• Due Date: Friday 12 December 2025, before 23:59 (Blackboard's clock).
• Team Size: 2 (pair design/programming)!
  Note that as of the 2017-2018 Academic Year, each International student should team up with "local" (i.e., whose Bachelor degree was obtained at the University of Antwerp).
• Submitting your solution:
  • Only one member of each team submits a full solution (ZIP file).
  • The other team member must submit a single (plain text or HTML) file containing only the names of both team members. This will allow us to put in grades for both team members in BlackBoard.
• Submission Medium: BlackBoard.
• Contact / TA: Rakshit Mittal.

Introduction

You will use (classic) DEVS to model a routing and batch processing system for a flexible job shop. A conceptual view of the system is shown here:

• Products move in the direction of the arrows.
• The distribution of the Inter Arrival Times (IAT) of products (from the "environment" or "source") is uniform. This arrival process is modelled in a Generator DEVS block. The details of this distribution are given below.
• Different product types follow different production routes through the machines.
• A machine may fit more than one product, so as long as it is not filled up to full capacity, it may wait for more products to arrive before starting the batch processing operation.
• At the end of the system, we have a Sink, where all products are collected, so we can extract statistics to analyse performance.

Specification

We now give an overview of the different DEVS components, and their behavior, and their parameters. Although many of the parameters are fixed, your solution must work with different parameters as well. In other words, don't hardcode the parameter values in your DEVS blocks!

Atomic DEVS blocks

• Generator
  • seed (int): Seed for the random number generator.
  • gen_rate (float): The average product generation rate (in products/second). This parameter is fixed at 1/60/4 = once every 4 minutes.
  • gen_types (list of tuples): The different product types to generate, specified as (product_type_id, size, recipe, processing_times, probability) tuples. This parameter is fixed at [(0, 1, ['A','B'], {'A': 900, 'B': 600}, 2/3), (1, 2, ['B','A'], {'A': 1200, 'B': 800}, 1/3)], meaning:
    • Type 0: size 1, route A→B, 15min at A and 10min at B, probability 2/3
    • Type 1: size 2, route B→A, 20min at B and 13.33min at A, probability 1/3
    Note: Products carry their own processing times (in seconds), so different product types can have different processing requirements at the same machine.
• Sink (collects finished products and determines termination)
  • target_num (int): The number of finished (non-spoiled) products required to terminate the simulation. This parameter is fixed at 500 for our analyses. The simulation continues until the Sink has received this many completed products.
• Router
  • machine_names (list of str): The different machines in the system. We will use ['A', 'B'].
  • routing_time_per_size (float, seconds): Time required to route a product per unit of size. For example, with routing_time_per_size = 30, a product of size 1 takes 30 seconds to route, and a product of size 2 takes 60 seconds. This parameter is fixed at 30 seconds.
  • dispatching_strategy (enum): The strategy to use when multiple products are waiting to be dispatched to the same machine. Two strategies will be implemented:
    • FIFORouter: Products are dispatched in First-In-First-Out order.
    • PriorityRouter: Products are dispatched by priority. The priority order is:
      1. Products further along in their recipe (higher current_step) get priority over newly arrived products. This ensures products already in progress complete their journey.
      2. Among products at the same step, larger products have priority over smaller products.
      3. Among products with the same step and size, earlier arrivals get priority.

  The Router reads each product's recipe (list of machine operations) and current step to determine where to send it next. When a product arrives from the Generator or from a Machine (after completing an operation), the Router checks:

  • If the product has more operations remaining in its recipe, dispatch it to the appropriate machine.
  • If the product has completed all operations in its recipe, send it to the Sink.

  The Router maintains an internal queue (buffer) of products waiting to be dispatched. This is a queuing system: products arrive, wait in the queue until they can be dispatched, and then are sent to machines or the sink. When a machine becomes available (has remaining capacity), and products in the queue need that machine for their next operation, the dispatching strategy determines which product is sent.

  Important: The Router must track which product type each machine is currently batching. A machine can only process products of the same type in a single batch. When dispatching products to a machine that already contains products, the Router must only send products matching the batch's product type. When a machine becomes empty again (capacity notification indicates full capacity), the batch type is reset and any product type can start a new batch.

  Queue statistics tracking: To enable analysis of the queuing system, your Router should track the average queue length. This requires tracking the total area under the queue length curve (queue_length × time_duration for each state) and dividing by the total simulation time.

• Machine
  • machine_id (str): The identifier of the machine, e.g., 'A' or 'B'.
  • capacity (int): Capacity of the machine. E.g., 3 for Machine A, 2 for Machine B.
  • max_wait_duration (float, seconds): When a machine is completely filled up (zero remaining capacity), the processing operation starts immediately. However, the operation may also start if the machine is non-empty, and a certain amount of time (the max_wait_duration) has passed since the first product has entered the machine. This parameter is that amount of time.
  • Processing time: The processing duration is determined by the product's processing_times attribute. When a machine starts processing a batch, it uses product.processing_times[machine_id] to determine how long the operation takes. Since machines can only batch products of the same type, all products in a batch have the same processing time.

    Important: Machines must validate that all products in a batch have the same product_type. If a product with a different type is added to an existing batch, the Machine should raise a ValueError (this indicates a bug in the Router logic).

    For simplicity, there is no time delay between sending the products back to the router and the machine becoming available again (at original capacity).

  • Statistics tracking: To enable performance analysis, your Machine must track total_processing_time, total_occupancy_product, and num_batches. These fields are pre-declared in MachineState. Update them in intTransition when starting batch processing.

The specification of the semantics of the Atomic DEVS blocks is entirely deterministic (given the same seed for the same psuedo-random number generator. Note that behavior may change between different Python versions, see this discussion).

Coupled DEVS

The system as a whole is modeled as a Coupled DEVS block. Its parameters are mostly passed as-is to the underlying Atomic DEVS blocks. They are:

• target_num (int) -> Sink (number of finished products required to terminate).
• gen_rate (float) -> Generator.
• gen_types (list of tuples) -> Generator. The Router and Machines don't need this parameter as products carry their own recipes and processing times.
• machine_capacities (dict) -> Each Machine its respective capacity. E.g., {'A': 3, 'B': 2}.
• dispatching_strategy (enum) -> Router.
• max_wait_duration (float) -> each Machine (same value for all machines).
• routing_time_per_size (float) -> Router (time per unit size for routing operations).

What is expected

First of all, you are given an implementation of the following AtomicDEVS blocks, which you must not edit:

• Generator
  • out_product (Product): output port on which an event is sent when a product is generated.
• Sink
  • in_product (Product): input port on which an event is sent when a product completes all operations. For each product, the time duration spent in the system is computed and stored.

You will:

• Implement the AtomicDEVS blocks for FIFORouter, PriorityRouter, and Machine.
• Think of the interfaces of these blocks (input/output ports and their events) and the protocol spoken by them.
• Finally, in the CoupledDEVS block representing the entire system, you will have to make the right connections (which of course depends on the input/output ports that you have defined in your AtomicDEVS).

An indication of the complexity: my own solution of the AtomicDEVS blocks is about 300 lines of code (including comments).

Goal: Performance Analysis

Once you have implemented the system, you will do performance analysis, comparing combinations of the following parameter values:

• max_wait_duration (float): we will try 0, 3, 6 minutes.
• dispatching_strategy (enum): we will try FIFO and Priority (prioritize larger products).
• system_configuration (enum): we will try "baseline", "add-new-machines", "double-capacity", and "double-speed".
  • baseline: Machine A (capacity 3), Machine B (capacity 2). Product type 0 has 15min/10min processing times at A/B, type 1 has 20min/13.33min at B/A.
  • add-new-machines: Machine A (capacity 3), Machine B (capacity 2), Machine A_new (capacity 3), Machine B_new (capacity 2). Same product processing times as baseline. Products can use machines A (or A_new) and B (or B_new).
  • double-capacity: Machine A (capacity 6), Machine B (capacity 4). Same product processing times as baseline.
  • double-speed: Machine A (capacity 3), Machine B (capacity 2). Product processing times are halved: type 0 has 7.5min/5min at A/B, type 1 has 10min/6.5min at B/A.

  Note: Processing times are defined in the product's processing_times attribute within gen_types. Different configurations use different gen_types to achieve different processing speeds.

More specifically, we would like to know under which (combinations of) parameter values the (avg/min/max) duration that products spend in the system is minimized. Also, we'd like to know if adding more machines is better than doubling capacity or doubling speed, or does it depend on the choices made for the other parameters? This analysis will help answer the investment question: should we buy new machines, upgrade existing machines to handle larger batches, or upgrade them to process faster?

In addition to flow time analysis, you should compute and analyze the following statistics for each parameter combination:

• Average queue length: The time-weighted average number of products waiting in the Router's queue throughout the simulation.
• Machine utilization: The percentage of time each machine spent processing products.
• Machine average occupancy: The average number of products in a machine while it was processing.

Included in the assignment is a gnuplot-script, that will render 3 types of plots:

• the flow time of every product
• a box-plot of the flow times in function of the max_wait_duration-parameter
• a frequency plot of the flow times

Each of these plots may give you different insights into the overall system's performance.

Getting Started

1. Clone the mosis25 branch of this git repository.
2. Under the assignment directory, you'll find the following files:
   • runner.py This script runs the simulation for all combinations of parameter values as described in the Performance Analysis section. It will generate .csv files with the time durations that each product has spent in the system. Every row is a product (500 products, so 500 rows total), and every column represents a different combination of parameters. It will also generate a plot.gnuplot file, which you can run with gnuplot as follows:

     gnuplot plot.gnuplot

     which will result in a number of SVG files containing plots of the CSV files.

     You are only allowed to make temporary changes (for debugging) to this file.

   • system.py Contains the full system, modeled as CoupledDEVS. You need to edit this file.
   • atomicdevs.py Contains skeletons for the AtomicDEVS blocks that you must implement. You need to edit this file.
   • environment.py Contains implementations of the Generator, Sink and Product types. You must not edit this file.
3. Write a report, where you:
   • explain and motivate the interfaces/protocol of the AtomicDEVS blocks
   • show the plotted results
   • interpret the plotted results
4. Submit via BlackBoard, a ZIP file, containing:
   • Your code (only the assignment directory)
   • Your report (PDF)
   • The generated CSV- and SVG-files
5. Deadline: Friday 12 December 2025, 23:59

Additional Task: Track Spoilage (10%)

Implement a spoilage mechanism for work-in-progress (WIP) products waiting in the Router's buffer. Products that have already been processed by at least one machine can become spoiled if they wait too long before being dispatched to their next machine.

Spoilage Rules:

• Fresh products (current_step = 0, not yet processed by any machine): never spoil. They can wait indefinitely in the router buffer.
• WIP products (current_step >= 1, already processed by at least one machine): can spoil if they wait too long in the router buffer.

Spoilage Thresholds:

The spoilage threshold depends on which machine last processed the product:

• Products returning from Machine A: spoilage_threshold = 20 minutes
• Products returning from Machine B: spoilage_threshold = 15 minutes

For example:

• Type 1 product (route A→B): After processing by Machine A, it can wait maximum 20 minutes in the router buffer before spoiling.
• Type 2 product (route B→A): After processing by Machine B, it can wait maximum 15 minutes in the router buffer before spoiling.

Implementation Requirements:

• Track when each WIP product enters the router buffer.
• Check for spoilage before dispatching. If a WIP product has waited longer than its spoilage threshold, mark it as spoiled.
• Spoiled products should still be sent to the Sink (they are not discarded), but marked as spoiled.
• The Sink should track and report:
  • Total number of spoiled products
  • Percentage of spoiled products
  • Average flow time for non-spoiled vs. spoiled products
• Your report should analyze how spoilage is affected by:
  • max_wait_duration parameter (does faster machine processing reduce spoilage?)
  • dispatching_strategy (does PriorityRouter reduce spoilage by prioritizing WIP?)
  • system_configuration (which investment strategy minimizes spoilage?)

Note: For this bonus task only, you are allowed to extend the Product class in environment.py to add fields for tracking spoilage (e.g., buffer_entry_time, last_machine, is_spoiled). You may also modify the Sink class to track spoilage statistics.

Attention!

You must stick to the rules of DEVS:

• The functions timeAdvance and outputFnc are purely getters! They must not mutate the DEVS state, or any variable, anywhere.
• The functions extTransition and intTransition may mutate ONLY the DEVS state.

Any violation of these rules results in an incorrect solution. Points will be subtracted.

Coding Conventions

Please follow these coding conventions:

• Write your AtomicDEVS methods always in the following order:
  • extTransition
  • timeAdvance
  • outputFnc
  • intTransition
  This reflects the order in which the methods are called by the simulator:
  • extTransition always has highest priority (can interrupt anything)
  • timeAdvance is called before outputFnc
  • outputFnc is called right before intTransition
• Input/output port attributes start with 'in_' and 'out_'

Tips

• To observe the changing State in the PyPDVES debug output, write __repr__-methods (or __str__-methods) for your State-classes.
• Work modularly and test modularly: build each component (Atomic DEVS model) in isolation and integrate only when all components have been fully tested.
• Test/debug your integrated solution with only one product (set target_num parameter to 1).
• Initially, make components deterministic (i.e., do not sample from a distribution).
• Even though the pseudo-random number stream may be deterministic and your simulations may (must!) be replicable, the output trace may not be intuitive. By using deterministic timings, you will be able to predict what the behaviour trace should be. This makes being the "testing oracle" easier.

Troubleshooting

Common mistakes include:

• did you forget to return self.state from intTransition or extTransition ?
• did you accidentally write to self.x instead of self.state.x ?
• did you modify the state in timeAdvance or outputFnc ? (NOT ALLOWED!!)

Extra Material

• This assignment was inspired by the queueuing example.
• You can find the documentation for PythonPDEVS here.