Robust dynamic and stochastic scheduling in permutation flow shops

Student thesis: Doctoral Thesis


The Permutation Flow Shop Scheduling Problem (PFSP) is a fundamental problem underlying many operational challenges in the field of logistic and supply chain management. The PFSP is a well-known NP-hard problem whereby the processing sequence of the jobs is the same for all machines. The dynamic and stochastic PFSP arise in practice whenever a number of different types of disruptions or uncertainties interrupt the system. Such disruptions could lead to deviate the disrupted schedule from its initial plan. Thus, it is important to consider different solution methods including: an optimisation model that minimise different objectives that take into account stability and robustness, efficient rescheduling approach, and algorithms that can handle large size and complex dynamic and stochastic PFSP, under different uncertainties. These contributions can be described as follows:

1. Develop a multi-objective optimisation model to handle different uncertainties by minimising three objectives namely; utility, instability and robustness.

2. Propose the predictive-reactive approach to accommodate the unpredicted uncertainties.

3. Adapt the Particle Swarm Optimisation (PSO), the Iterated Greedy (IG) algorithm and the Biased Randomised IG algorithm (BRIG) to reschedule the PFSP at the reactive stage of the predictive-reactive approach.

4. Apply the Simulation-Optimisation (Sim-Opt) approach for the Stochastic PFSP (SPFSP)under different uncertainties. This approach consists of two methods, which are: the novel approach that hybridise the Monte Carlo Simulation (MCS) with the PSO (Sim-PSO)and the Monte Carlo Simulation (MCS) with the BRIG (Sim-BRIG).

The main aim of using the multi-objective optimisation model with different solution methods is to minimise the instability and keep the solution as robust as possible. This is to handle uncertainty as well as to optimise against any worst instances that might arise due to data uncertainty. Several approaches have been proposed for the PFSP under dynamic and stochastic environments, where the PSO, IG and BRIG are developed for the PFSP under different uncertainties. Also, hybridised the PSO and the BRIG algorithms with the MCS to deal with SPFSP under different uncertainties. In our version of the approach, the first one is a PSO algorithm step after which an MCS is incorporated in order to improve the final solutions of problem. The second approach proposed the hybridisation of the BRIG algorithm with MCS to be applied on the SPFSP under different uncertainties. The developed multi-objective model and proposed approaches are tested on benchmark instances proposed by (Katragjini et al.,2013) in order to evaluate the effectiveness of the proposed methodologies, this benchmark is based on the well-known instances of Taillard’s (Taillard, 1993). The computational results showed that the proposed methodologies are capable of finding good solutions for the PFSP under different uncertainties and that they are robust for the dynamic and stochastic nature of the problem instances. We computed the best solutions and found that they could be highly promising in minimising the total completion time. The results obtained are quite competitive when compared to the other models found in the literature. Also, some proposed algorithms show better performance when compared to others.
Date of AwardJan 2018
Original languageEnglish
Awarding Institution
  • University of Portsmouth
SupervisorDjamila Ouelhadj (Supervisor) & Dylan Jones (Supervisor)

Cite this