Optimization Online


Migration from Sequence to Schedule in Total Earliness and Tardiness Scheduling Problem

Mohammad Namakshenas (m_namakshenas***at***ind.iust.ac.ir)
Mohammad Mahdavi Mazdeh (mazdeh***at***iust.ac.ir)

Abstract: To be competitive, services must be delivered with high punctuality. To schedule punctual services, the classical scheduling theory offers to minimize total earliness and tardiness of services. In this study, we developed an optimal fully polynomial time algorithm to transform a given sequence, permutation of jobs, into its minimum cost schedule counterpart, timing of jobs. We prove some fundamental properties on the discrete structures over sub-sequences of jobs, called clusters. The algorithm first decomposes a sequence into several clusters, and then it applies a recursive scheme to join the clusters and to generate their minimum cost schedule counterparts. The complexity status sheds light on the competitiveness of our algorithm in comparison with other state-of-the-art algorithms in the literature.

Keywords: Scheduling, Single machine, Total earliness and tardiness, Exact algorithm

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

Citation: 1

Download: [PDF]

Entry Submitted: 07/09/2019
Entry Accepted: 07/09/2019
Entry Last Modified: 02/20/2020

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