Paper Title:
Minimizing Total Earliness and Total Tardiness on Single Machine with Release Dates
  Abstract

This paper considers the bicriteria scheduling problem of minimizing the total earliness and the total tardiness on a single machine with release dates. In view of the fact that the problem has been characterized as NP-Hard, we propose two approximation algorithms (labeled as ETA1 and ETA2) for solving the problem. The proposed algorithms were compared with the MA heuristic selected from the literature. The two criteria (the total earliness and the total tardiness) were aggregated together into a linear composite objective function (LCOF). The performances of the algorithms were evaluated based on both effectiveness and efficiency. The algorithms were tested on a set of 1200 randomly generated single machine scheduling problems. Experimental results show that both the ETA1 and ETA2 algorithms outperformed (in terms of effectiveness and efficiency) the MA heuristic under all the considered problem sizes. Also, the ETA1 algorithm outperformed the ETA2 algorithm when the number of jobs (n) ranges between 20 and 500.

  Info
Pages
30-43
DOI
10.4028/www.scientific.net/JERA.5.30
Citation
E. O. Oyetunji, A. E. Oluleye, "Minimizing Total Earliness and Total Tardiness on Single Machine with Release Dates", International Journal of Engineering Research in Africa, Vol. 5, pp. 30-43, 2011
Online since
July 2011
Export
Price
$32.00
Share

In order to see related information, you need to Login.

In order to see related information, you need to Login.

Authors: Zhi Qiang Xie, Jing Yang, Yu Jing He, Guang Jie Ye
Abstract:Aiming at the dynamic integrated scheduling problem of complex multi-products with different arriving time and identical machines, an...
897
Authors: Si Lian Xie, Tie Bin Wu, Shui Ping Wu, Yun Lian Liu
Chapter 18: Computer Applications in Industry and Engineering
Abstract:Evolutionary algorithms are amongst the best known methods of solving difficult constrained optimization problems, for which traditional...
2846
Authors: Fang Li, Yu Wang, Ying Chun Zhong, Zhi Tan
Chapter 16: Application of Information and Network Technology
Abstract:An optimization of multi-varieties and small-batch of production scheduling is proposed, which is embodied the utilization ratio of...
3177
Authors: Hai Yan Wang
Chapter 6: Production Management
Abstract:This paper presents a hybrid algorithm to address the flexible job-shop scheduling problem (FJSP). Based on Differential Evolution (DE), a...
502
Authors: Sun Xin Wang, Yan Li, Yan Rong Zhang
Chapter 15: Economics, Marketing and Engineering Management
Abstract:In this paper a hybrid algorithm named IPSO-VND is proposed and applied to solving the vehicle routing problem with simultaneous pickup and...
2326