Robust scheduling of parallel machines considering total flow time

• We consider β-robust approach on parallel machine with Total Flow Time for the first time.
• We propose a branch and bound algorithm with particular branching procedure.
• For the first time we optimally solve β-robust scheduling problem up to 45 jobs.
• Our algorithm for a single machine is better and more efficient than previous works.

An effective approach to structuring uncertainty and making decisions under uncertain conditions is the robustness approach. The robust scheduling approach tries to create a schedule that minimizes the effect of disturbances caused by uncertainty during the operation on the objective function of initial scheduling. The present research was an attempt to study the problem of maximizing the probability that the total flow time does not exceed a predetermined limit in identical parallel machines while the processing time of each job is stochastic. In order to find an optimal solution to this problem, several theorems were proposed. The proposed theorems considerably reduced the search space and resulted in a branch and bound method to the problem with a specific branching scheme. Moreover, development of theorems to determine the dominance set along with introduction of dominance rules, an upper bound, and a lower bound helped find optimal solutions to the problems of 45 jobs and 5 machines. In addition, it was found that the method proposed in this paper for several machines is more effective than the methods developed for a single machine.