A genetic algorithm embedded with a concise chromosome representation for distributed and flexible job-shop scheduling problems

This paper proposes a genetic algorithm (GA_JS) for solving distributed and flexible job-shop scheduling (DFJS) problems. A DFJS problem involves three scheduling decisions: (1) job-to-cell assignment, (2) operation-sequencing, and (3) operation-to-machine assignment. Therefore, solving a DFJS problem is essentially a 3-dimensional solution space search problem; each dimension represents a type of decision. The (GA_JS) algorithm is developed by proposing a new and concise chromosome representation ({varvec{S}}_{{varvec{JOB}}}), which models a 3-dimensional scheduling solution by a 1-dimensional scheme (i.e., a sequence of all jobs to be scheduled). That is, the chromosome space is 1-dimensional (1D) and the solution space is 3-dimensional (3D). In (GA_JS), we develop a 1D-to-3D decoding method to convert a 1D chromosome into a 3D solution. In addition, given a 3D solution, we use a refinement method to improve the scheduling performance and subsequently use a 3D-to-1D encoding method to convert the refined 3D solution into a 1D chromosome. The 1D-to-3D decoding method is designed to obtain a “good” 3D solution which tends to be load-balanced. In contrast, the refinement and 3D-to-1D encoding methods of a 3D solution provides a novel way (rather than by genetic operators) to generate new chromosomes, which are herein called shadow chromosomes. Numerical experiments indicate that (GA_JS) outperforms the IGA developed by De Giovanni and Pezzella (Eur J Oper Res 200:395–408, 2010), which is the up-to-date best-performing genetic algorithm in solving DFJS problems.