Skip to Main content Skip to Navigation
Journal articles

Total completion time minimization for machine scheduling problem under time windows constraints with jobs’ linear processing rate function

Abstract : In this paper, we consider an identical parallel machine scheduling problem with a single additional resource. The processing rate of a job is defined by a linear resource consumption function. The addressed problem takes into consideration two new constraints. The first is the time-varying total available resource. The second new constraint limits the resource consumption incrementation of each job on two consecutive periods of time. Moreover, jobs have bounded resource consumption, arrival times and deadlines. Many practical applications, such as the electrical charging scheduling, can find interests in our works. Our contributions are two-folds. First, we introduce a Mixed-Integer-Linear-Program (MILP) to formulate the problem. Then, we present a heuristic consisting of two phases: a feasible solution construction phase using geometrical strip packing and a solution improvement phase. The heuristic is proven to be very efficiency for dealing with the problem throughout the numerical experiments.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02486133
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Thursday, February 20, 2020 - 4:33:29 PM
Last modification on : Monday, April 20, 2020 - 2:14:09 PM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Nhan-Quy Nguyen, Farouk Yalaoui, Lionel Amodeo, Hicham Chehade, Pascal Toggenburger. Total completion time minimization for machine scheduling problem under time windows constraints with jobs’ linear processing rate function. Computers and Operations Research, Elsevier, 2018, 90, pp.110-124. ⟨10.1016/j.cor.2017.09.015⟩. ⟨hal-02486133⟩

Share

Metrics

Record views

221