Paper Information

Journal:   JOURNAL OF INDUSTRIAL AND SYSTEMS ENGINEERING (JISE)   SPRING 2016 , Volume 9 , Number 2; Page(s) 1 To 19.
 
Paper: 

AN APPROXIMATION ALGORITHM AND FPTAS FOR TARDY/LOST MINIMIZATION WITH COMMON DUE DATES ON A SINGLE MACHINE

 
 
Author(s):  KIANFAR KAMRAN, MOSLEHI GHASEM*, SHAHANDEH NOOKABADI ALI
 
* DEPARTMENT OF INDUSTRIAL AND SYSTEMS ENGINEERING, ISFAHAN UNIVERSITY OF TECHNOLOGY, ISFAHAN, IRAN
 
Abstract: 

This paper addresses the Tardy/Lost penalty minimization with common due dates on a single machine. According to this performance measure, if the tardiness of a job exceeds a predefined value, the job will be lost and penalized by a fixed value. Initially, we present a 2-approximation algorithm and examine its worst case ratio bound. Then, a pseudo-polynomial dynamic programming algorithm is developed. We show how to transform the dynamic programming algorithm to an FPTAS using the technique of "structuring the execution of an algorithm" and examine the time complexity of our FPTAS.

 
Keyword(s): SINGLE MACHINE SCHEDULING, TARDY/LOST PENALTY, COMMON DUE DATE, APPROXIMATION ALGORITHM, FPTAS
 
References: 
  • ندارد
 
  pdf-File tarjomyar Yearly Visit 35
 
Latest on Blog
Enter SID Blog