Rate-Modifying 활동이 있는 병렬기계의 Makespan의 최소화를 위한 휴리스틱 방법

Abstract

In this research, we consider the problem of job scheduling and rate-modifying activities on parallel machines in order to minimize the makespan. A rate-modifying activity is an activity that changes the production rate of equipment. Typical example of rate-modifying activities is the maintenance of bad nozzles and the readjustment of PCB in a chip-shooter machine. We develop a heuristic to assign a group of jobs by considering the influence of the rate-modifying activities. The proposed algorithm consists of three steps; initialization, improvement by properties and improvement by searches. In initialization step, we categorize jobs into three groups and assign jobs group by group. In improvement by properties step, we improve the current solution by moving and exchanging jobs which satisfy the suggested properties. In improvement by search step, we improve the current solution by moving and exchanging jobs at the direction of the makespan minimization. The proposed heuristic is compared with existing branch and bound algorithm for small size problems. For large size problem, it is compared with existing heuristic, modified COMBINE (MCOM). The results indicate that the proposed heuristic deviates less than 10% from optimal in average for small size problems. For large size problems, the proposed heuristic improves MCOM 38% in average. Especially the proposed heuristic significantly improves MCOM when the variance of modifying rate of problem is relatively large.