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

Nhan Quy Nguyen (1) , Farouk Yalaoui (1) , Lionel Amodeo (1) , Hicham Chehade (1) , Pascal Toggenburger (2)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
2 Park'nPlug

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.

Mots clés: Total completion time; Strip packing; Resource allocation; Linear processing rate function

Domaines: Recherche opérationnelle [math.OC]

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, 2018, 90, pp.110-124. ⟨10.1016/j.cor.2017.09.015⟩. ⟨hal-02486133⟩