Exact algorithms for inventory constrained scheduling on a single machine

Exact algorithms for inventory constrained scheduling on a single machine

0.00 Avg rating0 Votes
Article ID: iaor20131942
Volume: 16
Issue: 1
Start Page Number: 105
End Page Number: 115
Publication Date: Feb 2013
Journal: Journal of Scheduling
Authors: , ,
Keywords: inventory, combinatorial optimization, programming: branch and bound, programming: dynamic
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.

Reviews

Required fields are marked *. Your email address will not be published.