A Genetic Algorithm Approach to Parallel Machine Scheduling Problems Under Effects of Position-Dependent Learning and Linear Deterioration: Genetic Algorithm to Parallel Machine Scheduling Problems

Introduction

In a parallel machine scheduling problem, there are n jobs that can be scheduled simultaneously on m different machines in parallel. In this paper, the effects of learning and deterioration on actual processing times of jobs are investigated in a parallel machine scheduling problem when the objective is to minimize the sum of completion times. The learning effect denotes that a constantly repeating of similar tasks on a machine or on a shop drives the worker or the system to complete the current task faster than the previously planned task duration. The learning effect can be dependent on the position of the job or the starting time of the job. This effect is a positive outcome because of constantly repeating of similar tasks on a machine or system. The deterioration effect denotes that actual processing time of a job has an increasing function that depends on its starting time. While waiting on a queue or being processed on a machine, the processing time of that job is increasing because of deterioration in scheduling environment. The most common real-life example of the deterioration effect is job processing on rolling machines. While waiting for rolling machines, the temperature of work-piece is decreasing so this work-piece must be reheated in order to be processed in rolling machines. The effects of learning and deterioration in a scheduling environment have opposite impacts on actual processing times of jobs. Most of the parallel machine scheduling problems are in NP-Hard class. Small or reasonably sized problems can be solved with any mathematical solution technique. However, using an exact solution algorithm or an inefficient heuristic method takes high running times for an optimal solution of a large-size problem. Metaheuristic algorithms such as genetic algorithm are more applicable for large-size problems and they yield near optimal solutions when proper algorithm parameters are used. In this study we proposed a GA for parallel machine scheduling problem under effects of learning and deterioration where the objective is to minimize sum of completion times. We generated some test problems considering different learning and deterioration effects for the problem. Furthermore, we compared our proposed GA algorithm with an existing simulated annealing (SA) algorithm for parallel machine scheduling problem.

The effects of learning and deterioration have been studied by researchers for more than 15 years. Biskup (1999) introduced the learning effect in scheduling problems as a pioneer. Mosheiov (2001) studied the learning effect on parallel machine environment. Furthermore, Mosheiov (2001) investigated several well-known performance criteria for the single machine under the learning effect. As far as we know, Gupta and Gupta (1988) and Browne and Yechiali (1990) made first studies about the deterioration effect. Mosheiov (1991) showed that the optimal schedule is V-shaped for single machine scheduling problem when the objective function is to minimize flow time. Mosheiov (1998) studied a scheduling problem with linear deterioration effect on identical parallel machines and proved that the problem is NP-Hard. One of the latest paper about learning and deterioration effects is studied by Toksarı and Arık (2017). They investigated fuzzy learning and deterioration effects with fuzzy processing times and they showed that for some well-known performance criteria, fuzzy single machine problems can be solvable in polynomial times by using credibility based fuzzy chance constraint programming technique.