Bilinear branch and check for unspecified parallel machine scheduling with shift consideration

Ponpot Jartnillaphand, Elham Mardaneh and Hoa T. Bui

European Journal of Operational Research, 2025, vol. 320, issue 1, 35-56

Abstract: This paper tackles the complex challenge of team formations, assignments, and job schedules within the static Unspecified Parallel Machine Flexible Resource Scheduling problem, specifically incorporating shift considerations. In existing literature, teams are often simplified as machines that operate continuously throughout the day without any interruptions. However, in reality, teams require breaks between shifts and cannot work continuously within a day. Therefore, we introduce shift considerations to ensure that teams do not work in consecutive shifts. We consider flexible workers, capable of performing any job, who are distributed among different teams in different shifts to undertake various jobs. The number of teams in each shift is a decision variable. The duration of each job is determined by the number of workers in a team assigned to it. The objective function is to minimize the makespan, representing the overall schedule completion time, while adhering to precedence constraints. We formulate an integer linear programming model for the proposed problem and develop a novel bilinear branch and check algorithm that introduces valid bilinear inequalities to accelerate convergence. The numerical results confirm that our algorithm’s performance optimally solves problems up to 35 jobs within a reasonable timeframe, surpassing the efficiency of the branch and cut method of IBM CPLEX and the classical branch and check algorithm.

Keywords: Scheduling; Parallel machine; Controllable job processing time; Shift consideration; Branch and check (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724006295
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:320:y:2025:i:1:p:35-56

DOI: 10.1016/j.ejor.2024.08.011

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().