Parallel-batching scheduling with nonlinear processing times on a single and unrelated parallel machines

Abstract

Parallel-batching processing and job deterioration are universal in the real industry. Scholars have deeply investigated the problem of parallel-batching scheduling and the problem of scheduling with deteriorating jobs separately. However, the situations where both parallel-batching processing and job deterioration exist simultaneously were seldom considered. This paper studies the parallel-batching scheduling problem with nonlinear processing times on a single machine, and proposes several structural properties and an optimal algorithm to solve it. Based on the above properties and optimal algorithm for the single machine setting, we further study the problem of parallel-batching scheduling with nonlinear processing times under the unrelated parallel machine setting. Since the unrelated parallel machines scheduling problem is NP-hard, a hybrid SFLA-VNS algorithm combining Shuffle Frog Leap Algorithm (SFLA) with Variable Neighborhood Search Algorithm (VNS) is proposed. Computational experiments and comparison are finally conducted to demonstrate the effectiveness of the proposed algorithm.