A two-stage heuristic algorithm for dynamic seru scheduling problems with resource constraints

Xiang, Yiran; Zhang, Zhe; Song, Xiaoling; Gong, Xue; Yin, Yong

doi:10.24200/sci.2024.62411.7826

A two-stage heuristic algorithm for dynamic seru scheduling problems with resource constraints

Articles in Press

Document Type : Research Article

Authors

Yiran Xiang ¹

Zhe Zhang ¹

Xiaoling Song ¹

Xue Gong ¹

Yong Yin ²

¹ School of Economics and Management, Nanjing University of Science and Technology, Nanjing, 210094, P. R. China

² Graduate School of Business, Doshisha University, Karasuma-Imadegawa, Kamigyo-ku, Kyoto, 602-8580, Japan

10.24200/sci.2024.62411.7826

Abstract

Originating from the Japanese electronics assembly industry, the seru production mode offers high efficiency, flexibility, and rapid responsiveness in manufacturing. This paper addresses the unspecified dynamic seru scheduling problem with resource constraints (UDSS-R), where resource usage must not exceed the available total at any given time. The UDSS-R problem is formulated as a mixed-integer linear programming (MILP) model aimed at minimizing the makespan. A two-stage heuristic algorithm is proposed subsequently: the first stage addresses the regular seru scheduling problem (without resource constraints) by assigning jobs to serus, and the second stage uses a dynamic programming algorithm based on the 0-1 knapsack problem to finalize the schedule. Computational experiments demonstrate the practicality and effectiveness of the proposed MILP model and the two-stage heuristic algorithm in solving the UDSS-R problem

Keywords

scheduling

seru production

dynamic

resource constraint

heuristic algorithm

Subjects