title: Complexity of line-seru conversion for different scheduling rules and two improved exact algorithms for the multi-objective optimization.
abstract: Productivity can be greatly improved by converting the traditional assembly line to a seru system, especially in the business environment with short product life cycles, uncertain product types and fluctuating production volumes. Line-seru conversion includes two decision processes, i.e., seru formation and seru load. For simplicity, however, previous studies focus on the seru formation with a given scheduling rule in seru load. We select ten scheduling rules usually used in seru load to investigate the influence of different scheduling rules on the performance of line-seru conversion. Moreover, we clarify the complexities of line-seru conversion for ten different scheduling rules from the theoretical perspective. In addition, multi-objective decisions are often used in line-seru conversion. To obtain Pareto-optimal solutions of multi-objective line-seru conversion, we develop two improved exact algorithms based on reducing time complexity and space complexity respectively. Compared with the enumeration based on non-dominated sorting to solve multi-objective problem, the two improved exact algorithms saves computation time greatly. Several numerical simulation experiments are performed to show the performance improvement brought by the two proposed exact algorithms.
authors.affiliation: Institute of Systems Engineering, Northeastern University, Shenyang, 110819 People's Republic of China.
authors.forename: Yang
authors.initials: Y
authors.lastname: Yu
authors.affiliation: Institute of Systems Engineering, Northeastern University, Shenyang, 110819 People's Republic of China.
authors.forename: Sihan
authors.initials: S
authors.lastname: Wang
authors.affiliation: College of Management Science and Engineering, Dongbei University of Finance and Economics, Shahekou, Dalian, 116026 People's Republic of China.
authors.forename: Jiafu
authors.initials: J
authors.lastname: Tang
authors.affiliation: Faculty of Environmental and Information Studies, Tokyo City University, Ushikubonishi 3-3-1, Yokohama, 224-8551 Japan.
authors.forename: Ikou
authors.initials: I
authors.lastname: Kaku
authors.affiliation: Business School, Liaoning University, Shenyang, 110316 People's Republic of China.
authors.forename: Wei
authors.initials: W
authors.lastname: Sun
keywords: Exact algorithm; Manufacturing; Scheduling rule; Space complexity; Time complexity