Exact algorithms for inventory constrained scheduling on a single machine
Publication date
2011-12-20
Document type
Forschungsartikel
Author
Organisational unit
Universität Siegen, Lehrstuhl für Wirtschaftsinformatik
Scopus ID
Publisher
Springer Science and Business Media LLC
Series or journal
Journal of Scheduling
ISSN
Periodical volume
16
Periodical issue
1
First page
105
Last page
115
Part of the university bibliography
Nein
Language
English
Keyword
Branch and bound
Dynamic programming
Inventory constraints
Machine scheduling
Abstract
This paper focuses on single machine scheduling subject to inventory constraints. Jobs add or remove items to or from the inventory, respectively. Jobs that remove items cannot be processed if the required number of items is not available. We consider scheduling problems on a single machine where the objective is to minimize the total weighted completion time. We develop properties of optimal solutions and design a branch and bound algorithm and a dynamic programming algorithm with two extensions. We compare the approaches in our computational study and empirically derive parameter settings leading to instances which are hard to solve. © 2011 Springer Science+Business Media, LLC.
Version
Published version
Access right on openHSU
Metadata only access