JOB-SHOP SCHEDULING TO MINIMIZE TOTAL WAITING TIME

This paper addresses the job-shop scheduling problem to minimize total waiting time. This also is equivalent to minimizing the work in process. Although, this problem is of relevance to manufacturing systems (Job-shops), most of the work in the literature concerns the minimization of makespan for which the algorithms proposed are implicit enumeration procedures. For the minimization of total waiting time, to our knowledge, there are only empirical priority rules, all of which construct non-delay schedules (i.e. there is no inserted idle time on the machines). In this work, we use theoretical results obtained for a single machine scheduling problem to construct an efficient heuristic for the problem at hand. This algorithm provides active schedules that are not always non-delay schedules. The convergence and the complexity of the algorithm are discussed. The performance is also evaluated with respect to a classical priority rule.