Job shop scheduling with unit processing times under uncertainties: Sequential flexibility and new lower-bound

This paper studies the Job Shop Scheduling Problem (JSSP) with Unit Processing Times evolving in an uncertain environment. Our aim is to determine a set of solutions instead of a unique solution in order to manage unanticipated events. To achieve this, an approach integrating two techniques is presented to achieve sequential flexibility. In the first time, the decomposition of the initial problem into sub-problems is exploited for producing a dominant schedule. Then, based on the Group Sequence (GS) method, a set of schedules is constructed, allowing for sequential flexibility with an evaluation of performance. The present work also develops a new lower bound for the GS and compares it with an existing lower bound from the literature. Using benchmark data sets, computational studies demonstrate that the suggested lower bound significantly outperforms the established lower bound found in the literature. In addition, our approach succeeded in finding a set of solutions for all tested benchmarks within a reasonable amount of CPU time. Moreover, two interesting flexibility indicators are presented to evaluate the efficacy of our approach.