A multi-agent resource bidding algorithm for order acceptance and assembly job shop scheduling

Abstract

This study uses an agent-based approach with a combinatorial auction mechanism to solve the joint order acceptance and assembly job shop scheduling problem. A set of jobs is offered. Each job has a revenue, ready time, due date, deadline, and consists of a set of operations with precedence relationships. Jobs that deviate from their due dates incur earliness/tardiness penalties. An operation may require several units of capacity per time unit and a resource could have multiple units of capacity. The manufacturer can reject any job to satisfy the capacity constraints and maximise the overall profit. We develop a mathematical model for the problem, then use an agent-based approach to solve it. First, the relaxed problem is decomposed into a set of job-level subproblems. Each job is optimised individually without considering the capacity constraints. Profitable jobs at the individual level submit their optimal schedules as combinatorial bids to an auctioneer to acquire combinations of resource capacity-time units. Then, the auctioneer records the profit upper bound, resolves capacity conflicts to reach a feasible solution, records the profit lower bound, and updates the dual variables. Experimental results show that the proposed methodology can solve large-sized problems in reasonable CPU times.

KEYWORDS:

• Assembly job shop scheduling
• order acceptance
• earliness and tardiness penalties
• Lagrangian relaxation
• agent-based combinatorial auctions
• just in time

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

The data that support the findings of this study are available from the corresponding author, OA, upon reasonable request.

Additional information

Funding

This work was supported by the College of Engineering ROCKET Seed Grant Program of Penn State University.

Notes on contributors

Omar Abbaas

Omar Abbaas received a dual-title Ph.D. degree in Industrial Engineering and Operations Research from the Pennsylvania State University in 2022. He is currently an Assistant Professor of Mechanical Engineering at the University of Texas at San Antonio. His research interests include operations research, supply chain management, transportation, energy, scheduling, and process improvement.

Jose A. Ventura

José A. Ventura received his Ph.D. degree in Industrial and Systems Engineering from the University of Florida in 1986. He is currently a Distinguished Professor of Industrial Engineering and Chair of the Interdisciplinary Operations Research Graduate Program at the Pennsylvania State University. He is a Fellow of IISE, the recipient of the 2018 David F. Baker Distinguished Research Award from IISE, and an Associate Editor of AIMS Environmental Science and Energies. His research interests include supply chain management, scheduling, transportation networks, and energy logistics.