Offline-Online Flexible Job-Shop Scheduling Problem makespan

This package is used to solve a Flexible Job-shop Scheduling Problem (FJSP) minimizing makespan through an offline and a MPC-based algorithm

Offline and Online Flexible Job-shop Scheduling Problem minimizing makespan

The two folders contain distinct algorithms designed to address the open-shop scheduling problem: an offline algorithm and an online algorithm based on Model Predictive Control (MPC). Both algorithms ensure robustness by effectively managing variations in processing time due to noises. The goal is to identify the solution that strikes the optimal balance between optimality and robustness.

For a more detailed explanation of the problem and its formulation, the user is kindly requested to refer to the two articles in the "Cite As" section, which contain the theoretical foundations of the implemented algorithm.

This package is designed to address the highly unconstrained open-shop problem, accommodating variations in the number of operations per job, possible machinery cycles, and flexible job routings. However, certain features such as setup time and preemption were not included in the current version. These may be considered in future releases. Interested parties are welcome to contact the author directly for potential collaborations.

Online MPC-based scheduling: The main function is "mpc_based_scheduling" and it is designed to solve an open-shop scheduling problem, with the objective of minimizing the makespan. Additionally, it incorporates automatic handling of shared machine allocation, management of cycles in the production process, and accommodation for varying lengths of production processes. The algorithm considers the scenario where jobs may arrive at a release time different from the planned schedule. It incorporates a prediction horizon to anticipate jobs expected to arrive shortly on the shop floor. The algorithm is activated each time a new job arrives, potentially rerouting existing jobs and preserving completed machine operations up to that point.

Parameters:

• G: The open-shop graph represented as a matrix, where each row corresponds to a scheduling alternative for a job. It is important to note that each row must have the same number of elements. So, if a job passes through fewer machines, the remaining columns must be filled with zero to maintain consistency.
• G_j: A vector that maps each i-th row of G to the corresponding i-th job schedule. It must have the same number of rows as G.
• P: The processing times matrix, where each element represents the processing time of job J on machine M. The matrix's size is JxM, where J is the number of jobs and M is the number of machines.
• BigOmega: values of noise intensity to test the production order with different delays
• Release_planned: The arrival time vector, containing the arrival time for each job.
• max_delay: mac advance/delay on a job with respect to planned relase time
• horizon: prediction horizon for MPC-scheduling

Offline scheduling: The main function is "offline_scheduling" and it is designed to solve an open-shop scheduling problem, with the objective of minimizing the makespan. Additionally, it incorporates automatic handling of shared machine allocation, management of cycles in the production process, and accommodation for varying lengths of production processes.

Parameters:

• G: The open-shop graph represented as a matrix, where each row corresponds to a scheduling alternative for a job. It is important to note that each row must have the same number of elements. So, if a job passes through fewer machines, the remaining columns must be filled with zero to maintain consistency.
• G_j: A vector that maps each i-th row of G to the corresponding i-th job schedule. It must have the same number of rows as G.
• P: The processing times matrix, where each element represents the processing time of job J on machine M. The matrix's size is JxM, where J is the number of jobs and M is the number of machines.
• BigOmega: values of noise intensity to test the production order with different delays
• S0: The arrival time vector, containing the arrival time for each job.

The supplementary files, namely "Compute_D_from_graph" and "pre_processing_graph", have the purpose of maintaining the main function's cleanliness by offloading specific computations and pre-processing tasks to separate modules.

The auxiliary files 'createGraphFromDataset' and 'generatePaths' simplify the process of generating feasible paths from an Excel file.