Minimizing makespan on a single-machine with release dates and inventory constraints

Minimizing makespan on a single-machine with release dates and inventory constraints


Operations Seminar by Morteza Davari (KU Leuven)
November 2018,  Tuesday 13 (12:30 pm) - N1 – Room 119

 

***

Abstract

We consider a single-machine scheduling problem with release dates and inventory constraints. Each job has a deterministic processing time and has an impact (either positive or negative) on the central inventory level. We aim to find a sequence of jobs such that the makespan is minimized while all release dates and inventory constraints are met. We show that the problem is strongly NP-hard even when the capacity of the inventory is infinite. To solve the problem, we introduce two mixed integer programming (MIP) formulations, a dynamic programming (DP) approach and also a branch-and-bound (B&B) algorithm.
This problem has some interesting applications in scheduling load/unload operations of warehouses. In a loading/unloading terminal, trucks arrive in a loading/unloading dock either to deliver (unload) or to pick up (load) a certain number of final products. The terminal include a storage space that is used to store these final products in inventory.

***