EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
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:00Room: 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
- Scheduling
- Game Theory
Status: accepted
Back to the list of papers