PARALLEL MACHINE SCHEDULING IN THE FACE OF PROCESSING TIME UNCERTAINTY

Abstract

Competition in today’s business and production world leads the companies to generate schedules that increase productivity and decrease manufacturing cost. However, most of the schedules cannot be executed exactly because of the unexpected disruptions such as machine breakdowns, order cancellations and so forth. In order to develop disruption resistant schedules, robust scheduling subject has gained interest among researchers. In this study, we consider a parallel machine environment with processing time uncertainty. The performance measure is taken as the completion time of the last job. The uncertainty is modeled by discrete set of scenarios. An integer programming model that can handle small problems is proposed. We observe that this model cannot manage large problems. To alleviate this difficulty, we propose to decrease number of scenarios selected for model. Next, we apply dual decomposition method in order to solve many smaller problems rather than a large problem. Large problems cannot be handled by this method either. This is why; we alter dual decomposition method by relaxing and develop a new heuristic. Also we propose a hybrid tabu search algorithm to solve the large problems.The results show that, the proposed heuristics; selecting scenario approach and tabu search algorithm perform well for the parallel machine scheduling problems.