Hybrid Queueing Theory and Scheduling Models for Dynamic Environments with Sequence-Dependent Setup Times

AAAI Conferences

Classically, scheduling research in artificial intelligence has concentrated on the combinatorial challenges arising in a large, static domain where the set of jobs, resource capacities, and other problem parameters are known with certainty and do not change. In contrast, queueing theory has focused primarily on the stochastic arrival and resource requirements of new jobs, de-emphasizing the combinatorics. We study a dynamic parallel scheduling problem with sequence-dependent setup times: arriving jobs must be assigned (online) to one of a set of resources. The jobs have different service times on different resources and there exist setup times that are required to elapse between jobs, depending on both the resource used and the job sequence. We investigate four models that hybridize a scheduling model with techniques from queueing theory to address the dynamic problem. We demonstrate that one of the hybrid models can significantly reduce observed mean flow time performance when compared to the pure scheduling and queueing theory methods. More specifically, at high system loads, our hybrid model achieves a 15% to 60% decrease in mean flow time compared to the pure methodologies. This paper illustrates the advantages of integrating techniques from queueing theory and scheduling to improve performance in dynamic problems with complex combinatorics.


Avalos-Rosales

AAAI Conferences

In this paper we propose an improved formulation for an unrelated parallel machine problem with machine and job sequence-dependent setup times that outperforms the previously published formulations regarding size of instances and CPU time to reach optimal solutions. The main difference between the proposed formulation and previous ones is the way the makespan has been linearized. It provides improved dual bounds which speeds up the solution process when using a branch-and-bound commercial solver. Computational experiments show that, using this model, it is possible to solve instances four times larger than what was previously possible using other mixed integer programming formulations in the literature and obtain optimal solutions on instances of the same size up to three orders of magnitude faster.


Local Search for Flowshops with Setup Times and Blocking Constraints

AAAI Conferences

Permutation flowshop scheduling problem (PFSP) is a classical combinatorial optimisation problem. There exist variants of PFSP to capture different realistic scenarios, but significant modelling gaps still remain with respect to real-world industrial applications such as the cider production line. In this paper, we propose a new PFSP variant that adequately models both overlapable sequence-dependent setup times (SDST) and mixed blocking constraints. We propose a computational model for makespan minimisation of the new PFSP variant and show that the time complexity is NP Hard. We then develop a constraint-guided local search algorithm that uses a new intensifying restart technique along with variable neighbourhood descent and greedy selection. The experimental study indicates that the proposed algorithm, on a set of wellknown benchmark instances, significantly outperforms the state-of-the-art search algorithms for PFSP.


An Efficient Memetic Algorithm for the Flexible Job Shop with Setup Times

AAAI Conferences

This paper addresses the flexible job shop scheduling problem with sequence-dependent setup times (SDSTFJSP). This is an extension of the classical job shop scheduling problem with many applications in real production environments. We propose an effective neighborhood structure for the problem, including feasibility and non improving conditions, as well as procedures for fast neighbor estimation. This neighborhood is embedded into a genetic algorithm hybridized with tabu search. We conducted an experimental study to compare the proposed algorithm with the state-of-the-art in the SDST-FJSP and also in the standard FJSP. In this study, our algorithm has obtained better results than those from other methods. Moreover, it has established new upper bounds for a number of instances.


A New Hybrid Genetic Algorithm for the Job Shop Scheduling Problem with Setup Times

AAAI Conferences

In this paper we face the Job Shop Scheduling Problem with Sequence Dependent Setup Times by means of a genetic algorithm hybridized with local search. We have built on a previous work and propose a new neighborhood structure for this problem which is based on reversing operations on a critical path. We have conducted an experimental study across the conventional benchmarks and some new ones of larger size. The results of these experiments show clearly that our approach outperforms the current state-of-the-art methods.