Bicriterion scheduling with truncated learning effects and convex controllable processing times
Ji‐Bo Wang, Dan‐Yang Lv, Jian Xu, Ping Ji, Fuqiang Li
Abstract
Abstract This paper investigates single‐machine scheduling in which the processing time of a job is a function of its position in a sequence, a truncation parameter, and its resource allocation. For a convex resource consumption function, we provide a bicriteria analysis where the first is to minimize total weighted flow (completion) time, and the second is to minimize total resource consumption cost. If the weights are positional‐dependent weights, we prove that three versions of considering the two criteria can be solved in polynomial time, respectively. If the weights are job‐dependent weights, the computational complexity of the three versions of the two criteria remains an open question. To solve the problems with job‐dependent weights, we present a heuristic (an upper bound) and a branch‐and‐bound algorithm (an exact solution).