Premium
Bicriterion scheduling with truncated learning effects and convex controllable processing times
Author(s) -
Wang JiBo,
Lv DanYang,
Xu Jian,
Ji Ping,
Li Fuqiang
Publication year - 2021
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12888
Subject(s) - mathematical optimization , computer science , regular polygon , heuristic , scheduling (production processes) , time complexity , convex function , function (biology) , exponential function , job shop scheduling , truncation (statistics) , single machine scheduling , mathematics , algorithm , machine learning , mathematical analysis , schedule , geometry , evolutionary biology , biology , operating system
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).