Bicriterion scheduling with truncated learning effects and convex controllable processing times

Ji Bo Wang, Dan Yang Lv, Jian Xu, Ping Ji, Fuqiang Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 Citations (Scopus)

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).

Original languageEnglish
Pages (from-to)1573-1593
Number of pages21
JournalInternational Transactions in Operational Research
Volume28
Issue number3
DOIs
Publication statusPublished - May 2021

Keywords

  • branch-and-bound
  • combinatorial optimization; heuristics
  • controllable processing time
  • scheduling
  • truncated learning effect

ASJC Scopus subject areas

  • Business and International Management
  • Computer Science Applications
  • Strategy and Management
  • Management Science and Operations Research
  • Management of Technology and Innovation

Cite this