A column generation-based exact solution method for seru scheduling problems. (April 2022)

• Record Type: Journal Article
• Authors: Zhang, Zhe; Gong, Xue; Song, Xiaoling; Yin, Yong; Lev, Benjamin; Chen, Jie
• Is Part Of: Omega. Volume 108(2022)
• Publication Date: 2022-04
• Subjects: Seru scheduling -- Dantzig-Wolfe decomposition -- Column generation -- Branch-and-bound; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2021.102581
• Languages: English
• ISSNs: 0305-0483

Abstract

Highlights: A new-type seru production system is introduced, and the seru scheduling problem to minimize the total weighted completion is studied. The integer programming model for seru scheduling problems is presented and reformulated, and a general column generation-based exact solution method is proposed. The report of results from computational experiments indicates that the proposed solution methodology is effective in solving seru scheduling problems, especially for the one with the appropriate ratio of jobs and serus. Abstract: This paper attempts to address production scheduling problems in seru production systems (SPS), which is a new-type manufacturing system emanating from Japanese electronic assembly industry. As a typical parallel production system, SPS has high efficiency, good flexibility, and rapid responsiveness, which are achieved by reconfiguring serus, increasing, or decreasing workers to adjust the output in practical volatile markets. The seru scheduling problem in this paper is formulated as an integer programming (IP) model to minimize the total weighted completion time (TWCT). Then, by employing the Dantzig-Wolfe decomposition, the proposed IP model is reformulated into a set partitioning problem with a master problem and several subproblems. A branch-and-bound (B&B) algorithm is designed, and each node in a B&B tree is a linear relaxation problem (LRP) of the set partitioning problem. The LRP is solved by a column generation approach, in which each column is generated to represent a schedule of the seru in SPS based on solving the subproblems. Computational experiments are conducted, and the results indicate that the proposed column generation-based exact solution method is promising in solving the seru scheduling problem effectively.