Optimization Online


Minimizing Earliness and Tardiness on a Single Machine with a Periodically Supplied Non-renewable Resource

Mohammad Namakshenas (m_namakshenas***at***ind.iust.ac.ir)
Aleida Braaksma (a.braaksma***at***utwente.nl)
Mohammad Mahdavi Mazdeh (mazdeh***at***iust.ac.ir)

Abstract: We consider a special class of single machine scheduling problem with partially overlapping processing times and a periodically supplied non-renewable resource. The objective is to minimize the sum of total tardiness and total earliness. Some properties and complexity results of the feasible and optimal schedules are discussed, then they are used to develop both a mathematical model and a decomposition-based polynomial-time approximation algorithm. We also develop an optimal polynomial-time algorithm for converting an optimal sequence into an optimal schedule in the context of the earliness-tardiness objective. The scalability tests analysis indicates the promising performance guarantee of the algorithm compared to provable optimal schedules.

Keywords: Scheduling, Single machine, Tardiness and earliness, Non-renewable resource

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Combinatorial Optimization (Approximation Algorithms )

Citation: 1

Download: [PDF]

Entry Submitted: 06/02/2019
Entry Accepted: 06/03/2019
Entry Last Modified: 06/03/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society