EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1741. A Game Theoretic Approach for Solving Lot Scheduling Problems

Invited abstract in session TD-36: Game Theory, Solutions and Structures VIII, stream Game Theory, Solutions and Structures.

Tuesday, 14:30-16:00
Room: 32 (building: 306)

Authors (first author is the speaker)

1. Shani Alkoby
Industrial engineering and Management, Ariel University
2. Baruch Mor
Department of Economics and Business Administration, Ariel University

Abstract

Lot scheduling problems are a significant focus in scheduling theory due to their broad applications and effect on operational efficiency. Traditionally, research in this field assumes a knowledgeable scheduler and truthful agents. However, this study delves into a more realistic scenario where these assumptions are challenged, proposing a game theory approach to handle the complexities arising from incomplete information and strategic behavior. We examine lot scheduling scenarios with uniform capacities for lots comprising orders of varying sizes. Departing from the conventional paradigm, we introduce the concept of a scheduler with limited information and agents prone to providing misleading information for personal gain. We investigate five fundamental objective functions in lot scheduling: (i) minimizing the completion time of the last job exiting the system, (ii) minimizing the total completion time, (iii) minimizing the total weighted completion time, (iv) minimizing the number of tardy orders, and (v) minimizing the total weighted number of tardy orders. Notably, we show that problems (i) to (iv) can be efficiently solved in polynomial time, while problem (v) is solvable in pseudo-polynomial time. Our research advances the understanding of decentralized scheduling, where agents' behavior and information gaps affect decision-making. It underscores the need to address real-world complexities in scheduling theory and provides insights for designing adaptable algorithms.

Keywords

Status: accepted


Back to the list of papers