European Journal of Operational Research, ( ISI ), Volume (286), No (1), Year (2020-10) , Pages (115-128)

Title : ( Minimizing makespan on a single machine with release dates and inventory constraints )

Authors: Morteza Davari , Mohammad Ranjbar , Patrick De Causmaecker , Roel Leus ,

Citation: BibTeX | EndNote

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 a time-indexed formulation and a sequence-based formulation, a branch-and-bound algorithm, and a dynamic- programming-based guess- and-check (GC) algorithm. From extensive computational experiments, we find that the GC algorithm outperforms all other alternatives.

Keywords

, Single-machine scheduling, Inventory constraint, Complexity, Branch-and-bound, Dynamic programming, Lagrangian relaxation
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

@article{paperid:1079818,
author = {مرتضی داوری and Ranjbar, Mohammad and پارتیک دی کاسمیکر and رول لویس},
title = {Minimizing makespan on a single machine with release dates and inventory constraints},
journal = {European Journal of Operational Research},
year = {2020},
volume = {286},
number = {1},
month = {October},
issn = {0377-2217},
pages = {115--128},
numpages = {13},
keywords = {Single-machine scheduling; Inventory constraint; Complexity; Branch-and-bound; Dynamic programming; Lagrangian relaxation},
}

[Download]

%0 Journal Article
%T Minimizing makespan on a single machine with release dates and inventory constraints
%A مرتضی داوری
%A Ranjbar, Mohammad
%A پارتیک دی کاسمیکر
%A رول لویس
%J European Journal of Operational Research
%@ 0377-2217
%D 2020

[Download]