Memetic algorithm for unrelated parallel machine scheduling problem with grey processing times

Purpose This paper aims to provide a promising memetic algorithm (MA) for an unrelated parallel machine scheduling problem with grey processing times by using a simple dispatching rule in the local search phase of the proposed MA. Design/methodology/approach This paper proposes a MA for an unrelated parallel machine scheduling problem where the objective is to minimize the sum of weighted completion times of jobs with uncertain processing times. In the optimal schedule of the problem's single machine version with deterministic processing time, the machine has a sequence where jobs are ordered in their increasing order of weighted processing times. The author adapts this property to some of their local search mechanisms that are required to assure the local optimality of the solution generated by the proposed MA. To show the efficiency of the proposed algorithm, this study uses other local search methods in the MA within this experiment. The uncertainty of processing times is expressed with grey numbers. Findings Experimental study shows that the MA with the swap-based local search and the weighted shortest processing time (WSPT) dispatching rule outperforms other MA alternatives with swap-based and insertion-based local searches without that dispatching rule. Originality/value A promising and effective MA with the WSPT dispatching rule is designed and applied to unrelated parallel machine scheduling problems where the objective is to minimize the sum of the weighted completion times of jobs with grey processing time.

Automated summary

This paper presents a promising memetic algorithm for an unrelated parallel machine scheduling problem by using a simple dispatching rule. The experimental study shows that the proposed algorithm outperforms other alternatives in terms of solution quality.