A Heuristic-Based Evolutionary Approach for Joint Optimization of Job Shop Scheduling and Facility Layout

Abstract

Job shop scheduling (JSS) aims to arrange the processing sequence of a series of operations to optimize the cost objective. The most common objective is to minimize the makespan without considering the flow time of materials between machines. However, in practical production scenarios, the material flow time directly affects the completion time of operations. Besides, facility layout (FL) is the premise of JSS. FL problem can be stated as assigning a range of production machines into the physical environment of the shop floor, which largely determines the time cost of material flow between machines. The result of FL will affect subsequent JSS. Therefore, the FL problem and the JSS problem naturally constitute a two-stage joint optimization problem. So far, the above-mentioned joint optimization problem is rarely studied in the literature because of the complexity of the problem. For this purpose, the joint optimization problem of FL and JSS is defined in this paper, called JSSFLP. Then, a hybrid heuristic evolutionary strategy (HHE) is proposed for solving the proposed JSSFLP. HHE consists of the meta-heuristic, the hyper-heuristic evolutionary algorithm, and the joint optimization mechanism (JOP), Among them, ant colony system (ACS), as a meta-heuristic algorithm, is used to solve the FL problem effectively, and genetic programming (GP), as a hyper-heuristic algorithm, is used to generate rule-based dispatching methods for JSS problem. Besides, JOP, as an adaptor, is designed to coordinate ACS and GP to solve JSSFLP cooperatively. Numerical experiments are conducted to demonstrate the feasibility and effectiveness of the proposed HHE and its component, respectively.

Keywords

• Job shop scheduling problem
• facility layout problem
• ant colony system
• genetic programming
• dispatching rule