two meta-heuristic algorithms for Parallel Machines Scheduling Problem with Past-Sequence-Dependent Setup Times and Effects of Deterioration and Learning

This paper addresses an identical parallel machines scheduling problem with past-sequence-dependent setup times, deteriorating jobs and learning effects, in which the actual processing time of a job on each machine is given as a function of the processing times of the jobs already processed and its scheduled position on the corresponding machine. In addition, the setup time of a job on each machine is proportional to the actual processing time of the already processed jobs on the corresponding machine, i.e., the setup time of a job is past-sequence-dependent (p-s-d). The objective is to determine jointly the jobs assigned to each machine and the order of jobs such that the total completion time is minimized. Since the problem is strongly NPhard, exact solution approaches are inefficient for realistic size problems. Thus, two meta-heuristic algorithms including artificial immune system (AIS) and ant colony optimization algorithm (ACO) are proposed to solve the given problem. The performance of the proposed algorithms are evaluated by solving a set of test problems. The computational results demonstrate that the proposed algorithms are effective and appropriate approaches to find solutions as good as exact algorithms, but when the size of the problem is increased, the AIS algorithm obtains better results in comparison with ACO algorithm.

کلیدواژه ها:

Scheduling ، Deteriorating jobs ، Learning effect ، setup times ، Artificial immune system ، Ant colony optimization