Authors: Kong, Min
Liu, Xinbao
Pei, Jun
Pardalos, Panos
Mladenović, Nenad 
Title: Parallel-batching scheduling with nonlinear processing times on a single and unrelated parallel machines
Journal: Journal of Global Optimization
Issue Date: 1-Jan-2018
Rank: M21
ISSN: 0925-5001
DOI: 10.1007/s10898-018-0705-3
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.
Keywords: Meta-heuristic algorithm | Nonlinear processing times | Parallel-batching | Scheduling
Publisher: Springer Link

Show full item record


checked on Jun 11, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.