DEVELOPMENT OF OPTIMUM PARALLEL MACHINES SCHEDULING MODEL SUBJECT TO MACHINES AVAILABILITY CONSTRAINT

Abstract

In machine-shop environments, machines are usually subject to down periods, which may be deterministic (as in the case of a planned preventive maintenance) or stochastic (as in the case of a sudden machine breakdown or unexpected material shortage). In this study, parallel machines makespan minimization problem, where the jobs are non-resumable and the machines are subject to unavailability periods of known starting times and durations, is considered. The problem was formulated as an Integer Linear Programming mathematical model. An efficient solution procedure is then proposed for the problem through two algorithms. The first algorithm utilizes the Longest Processing Time dispatching rule which generates an initial solution (makespan) used to obtain an upper bound. The upper bound is then used to backtrack through a second algorithm which adopted the greedy algorithm approach to achieve iteratively an optimal solution for the scheduling problem. The developed algorithms were implemented using Visual Basic programming language to facilitate the solution procedure. The developed software was validated using a typical numerical example while the model was evaluated using two industrial problems as case studies. The makespans obtained for the first and second case studies using the developed model are, respectively, about 49% and 40% lower than the makespan when the jobs were carried out in the industry. This showed that, in the long run, the model would efficiently serve machine shops in machines-jobs scheduling problem.