An effective discrete differential evolution algorithm for scheduling uniform parallel batch processing machines with non-identical capacities and arbitrary job sizes

Shengchao Zhou, Ming Liu, Huaping Chen and Xueping Li

International Journal of Production Economics, 2016, vol. 179, issue C, 1-11

Abstract: Batch processing machines (BPMs) simultaneously process multiple jobs in a batch, which are commonly used in many industrial systems. This paper studies the scheduling problem of uniform parallel batch processing machines with arbitrary job sizes. These batch processing machines have non-identical capacities and different speeds. The objective is to minimize the makespan (or maximize the machine utilization). We formulate this problem as a mixed integer programming model. Since the problem is strongly NP-hard, an effective differential evolution-based hybrid algorithm is proposed for solving large-scale problems. Firstly, in this algorithm, individuals in the population are represented as discrete job sequences, and novel mutation and crossover operators are designed based on this representation. Next, a heuristic is developed to form batches and schedule the resulting batches on the uniform parallel machines. Then, the performance of the proposed algorithm is evaluated by comparing its results to a commercial solver (CPLEX), a random keys genetic algorithm (RKGA) and a particle swarm optimization (PSO) algorithm. Experimental results demonstrate the superiority of the proposed algorithm in terms of solution quality and robustness, especially for large-scale instances.

Keywords: Scheduling; Batch processing machines (BPMs); Uniform parallel machines; Non-identical capacities; Discrete differential evolution algorithm (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0925527316300810
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:proeco:v:179:y:2016:i:c:p:1-11

DOI: 10.1016/j.ijpe.2016.05.014

Access Statistics for this article

International Journal of Production Economics is currently edited by Stefan Minner

More articles in International Journal of Production Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu ().