Minimising total earliness and tardiness with periodically supplied non-renewable resource profiles

Mohammad Namakshenas, Aleida Braaksma, Mohammad Mahdavi Mazdeh*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

We consider a special class of resource-constrained single machine scheduling problems. In the classical scheduling context, resource types are classified into renewable and non-renewable; however, a large variety of real-world problems may not fit into one of these classes, e.g. labour regulations in project scheduling, budget allocation to different phases of a construction project, and dose management in a medical imaging centre. In this study, we address a class of non-renewable resources supplied, not necessarily immediately, in different periods of the planning horizon. The objective is to assign the jobs to the supply periods and schedule them such that the sum of total tardiness and total earliness is minimised. Several properties and complexity results of the optimal schedules are discussed, then they are used to develop a tractable algorithm. First, we decompose the problem into several single supply problems and then decide the optimal schedule through a polynomialtime optimal algorithm for each single supply problem. The scalability tests indicate the promising performance guarantee of the algorithm compared to provably optimal schedules in the integrated framework.
Original languageEnglish
Number of pages12
JournalInternational journal of production research
Early online date17 Apr 2021
DOIs
Publication statusE-pub ahead of print/First online - 17 Apr 2021

Keywords

  • Scheduling
  • Single machine
  • Total earliness and tardiness
  • Non-renewable resource

Fingerprint

Dive into the research topics of 'Minimising total earliness and tardiness with periodically supplied non-renewable resource profiles'. Together they form a unique fingerprint.

Cite this