2797. Just-in-Time Batch Scheduling Subject to Batch Size
Invited abstract in session WA-12: Batch scheduling, stream Scheduling and Project Management.
Wednesday, 8:30-10:00Room: Clarendon SR 1.02
Authors (first author is the speaker)
| 1. | Sergey Polyakovskiy
|
| Deakin University | |
| 2. | Rym M'Hallah
|
| Engineering, King's College London |
Abstract
This paper considers single-machine just-in-time scheduling of jobs that may be grouped into batches subject to a constraint on batches’ weights. A job has a weight, due date, and earliness and tardiness penalties per unit time. A batch’s processing time is determined by its jobs. Each job inherits its batch’s completion time. The objective is to minimize the weighted sum of earliness and tardiness penalties of all jobs. This problem is challenging: Jobs-to-batch assignment changes the batch’s processing time; thus, affects the structure of the entire solution and most importantly of its cost components. To obtain tight dual bounds, we propose a Lagrangian relaxation approach that drops the constraint enforcing the use of each job exactly once and reformulates the problem as the shortest path problem to build a dual solution. To find exact solutions, we incorporate Lagrangian relaxation into a branch-and-bound approach to strengthen relaxation in each node of the search tree. We complement our research with the analysis of computational experiments that evaluate the tightness of our primal and dual bounds.
Keywords
- Scheduling
- Programming, Mixed-Integer
- Combinatorial Optimization
Status: accepted
Back to the list of papers