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.