Flow Time vs Work In Progress: Benchmark of Algorithms for the Online-Time Job Shop Scheduling Problem

The online-time Job Shop Scheduling Problem provides a useful model for real- time scheduling in industrial settings. In this problem, jobs with precedence constraints arrive according to a Poisson process, and resolution algorithms must generate a schedule at any given time. Two of the most insightful efficiency cri- teria to evaluate a schedule in an industrial context are flow time and work in progress, respectively the duration from a job’s arrival to its completion and the number of jobs being processed at any time. This paper aims to compare the performance for these two criteria of solution algorithms, notably rescheduling algorithms and priority dispatching rules. In order to enhance rescheduling poli- cies performances, a new objective function, termed the “fee-reward objective function”, is implemented in order to find a balance between both flow time and work in progress. The studied algorithms using the fee-reward objective func- tion show significantly better performances on the work in progress criterion and achieve comparable or even superior results on the flow time criterion rela- tive to the best priority dispatching rules and rescheduling algorithms using the makespan objective function.