Article ID: | iaor201111468 |
Volume: | 39 |
Issue: | 7 |
Start Page Number: | 1652 |
End Page Number: | 1660 |
Publication Date: | Jul 2012 |
Journal: | Computers and Operations Research |
Authors: | Leus Roel, Ranjbar Mohammad, Davari Morteza |
Keywords: | production, scheduling, combinatorial optimization, stochastic processes |
Uncertainty is an inevitable element in many practical production planning and scheduling environments. When a due date is predetermined for performing a set of jobs for a customer, production managers are often concerned with establishing a schedule with the highest possible confidence of meeting the due date. In this paper, we study the problem of scheduling a given number of jobs on a specified number of identical parallel machines when the processing time of each job is stochastic. Our goal is to find a robust schedule that maximizes the customer service level, which is the probability of the makespan not exceeding the due date. We develop two branch‐and‐bound algorithms for finding an optimal solution; the two algorithms differ mainly in their branching scheme. We generate a set of benchmark instances and compare the performance of the algorithms based on this dataset.