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

摘要

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. (c) 2017 Elsevier Ltd. All rights reserved.