Scheduling identical parallel batch processing machines involving incompatible families with different job sizes and capacity constraints. (July 2022)

• Record Type: Journal Article
• Authors: Li, Chunhao; Wang, Feng; Gupta, Jatinder N.D.; Chung, Tsuiping
• Is Part Of: Computers & industrial engineering. Volume 169(2022)
• Publication Date: 2022-07
• Subjects: Identical parallel batch processing machines with capacity constraints -- Incompatible job families -- Non-identical job sizes -- Arbitrary job release times -- Constraint-guided artificial immune system based algorithm; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2022.108115
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: We consider the identical parallel machine problem with incompatible families. We propose an improved heuristic algorithm to simultaneously consider various constraints. Proposed algorithm restricts the job insertions to improve its performance. We show that proposed algorithm is superior to existing algorithms. We suggest some directions for fruitful future research. Abstract: This paper investigates the problem of scheduling jobs on parallel batch processing machines with incompatible job families, non-identical job sizes, arbitrary job release times, and machine capacity constraints. A mixed-integer linear programming (MILP) model is established to minimize makespan. A lower bound is proposed to test the solution quality obtained from heuristic and metaheuristic algorithms. Since the problem is strongly NP-hard, we propose five constructive and polynomially bounded heuristic algorithms. To improve the solutions obtained by these constructive algorithms, we describe a job family constraint-guided artificial immune system (CGAIS) based algorithm. In the proposed CGAIS algorithm, only jobs in the same family can be executed by the secondary immune response. The longest batch processing time rule is used to form the batches. The effectiveness of the proposed constructive and the CGAIS algorithms is empirically tested on the randomly generated problem instances. These computational results show that the proposed CGAIS algorithm can obtain better near-optimal solutions than the existing algorithms.