Logo image
Back
A column generation-based exact solution method for seru scheduling problems
Journal article   Peer reviewed

A column generation-based exact solution method for seru scheduling problems

Zhe Zhang, Xue Gong, Xiaoling Song, Yong Yin, Benjamin Lev and Jie Chen
Omega (Oxford), v 108, 102581
Apr 2022
DOI: https://doi.org/10.1016/j.omega.2021.102581
Featured in Collection :   UN Sustainable Development Goals @ Drexel

Abstract

Branch-and-bound Column generation Dantzig-Wolfe decomposition Seru scheduling
•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. 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.

Metrics

15 Record Views
39 citations in Web of Science
40 citations in Scopus

Details

UN Sustainable Development Goals (SDGs)

This publication has contributed to the advancement of the following goals:

#12 Responsible Consumption & Production

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Collaboration types
Domestic collaboration
International collaboration
Web of Science research areas
Management
Operations Research & Management Science
Logo image