A Genetic Algorithm Enhanced by Tabu Search for the Single Machine Scheduling Problem with Deteriorating Jobs

Yue Yue Liu; Rui Zhang

doi:10.4028/www.scientific.net/AMR.774-776.1842

Paper Titles

The Exponent Set of a Class of Two-Colored Digraphs with One Common Vertex
p.1823

Comparison between Normalized Databases Implemented with Different Database Systems
p.1827

An Algorithm for Global Multi-Resolution Terrain Simulation Based on the Method of Hash Table
p.1833

Query Expansion Based on Books Tags of User’s Social Relations in XML Book Search
p.1838

A Genetic Algorithm Enhanced by Tabu Search for the Single Machine Scheduling Problem with Deteriorating Jobs
p.1842

Grey-Hierarchy Relation Analysis and Evaluation of Port Operating Ability
p.1847

A Portable Weather Station Design Applied in the Smart City
p.1853

The Visualization of Soil Moisture Based on VB and Surfer
p.1859

An Algorithm to Detect Noised Pixel in Image
p.1865

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 774-776A Genetic Algorithm Enhanced by Tabu Search for...

A Genetic Algorithm Enhanced by Tabu Search for the Single Machine Scheduling Problem with Deteriorating Jobs

Abstract:

This paper considers a single machine scheduling problem with deterioration and no inserted idle times. Each job has a due date, a weight and a processing time. The objective is to find an optimal sequence of the set of jobs to minimize the total weighted tardiness. To prevent premature convergence of the optimization algorithm, a genetic tabu search (GTS) algorithm is presented. In the GTS, the mutation operator is implemented with the tabu search method to enhance the local search ability. A fair comparison of genetic operators has been made between GTS and simple GA, and the experimental results show that the GTS considerably outperforms the simple GA.

You might also be interested in these eBooks

Advanced Technologies in Manufacturing, Engineering and Materials

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 774-776)

Pages:

1842-1846

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.774-776.1842

Citation:

Cite this paper

Online since:

September 2013

Authors:

Yue Yue Liu, Rui Zhang

Keywords:

Deteriorating Jobs, Genetic Algorithm (GA), Single Machine Scheduling, Tabu Search

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] B. Alidaee, N.K. Womer: Scheduling with time dependent processing times: review and extensions, Journal of the Operational Research Society 50: 711-720, (1999).

DOI: 10.1057/palgrave.jors.2600740

Google Scholar

[2] J.N.D. Gupta, S.K. Gupta: Single facility scheduling with nonlinear processing times, Computers & Industrial Engineering 14: 387-393, (1988).

DOI: 10.1016/0360-8352(88)90041-1

Google Scholar

[3] S. Browne, U. Yechiali: Scheduling deteriorating jobs on a single processor, Operations Research 38: 495-498, (1990).

DOI: 10.1287/opre.38.3.495

Google Scholar

[4] A. Bachman, A. Janiak: Minimizing maximum lateness under linear deterioration, European Journal of Operational Research, 126: 557-566, (2000).

DOI: 10.1016/s0377-2217(99)00310-0

Google Scholar

[5] A. Bachman, A. Janiak, M.Y. Kovalyov: Minimizing the total weighted completion time of deteriorating jobs, Information Processing Letters, 81: 81-84, (2002).

DOI: 10.1016/s0020-0190(01)00196-x

Google Scholar

[6] T.C.E. Cheng, W. -C. Lee, C. -C. Wu: Single-machine scheduling with deteriorating functions for job processing times, Applied Mathematical Modelling. 34: 4171-4178, (2010).

DOI: 10.1016/j.apm.2010.04.014

Google Scholar

[7] P. Guo, W. Cheng, Z. Zhang: Improved Genetic Algorithm for Single Machine Scheduling Problems with Deteriorating Jobs, Journal of Southwest Jiaotong University, 46: 506-511, (2011).

Google Scholar

[8] C. -S. Chung, J. Flynn, O. Kirca: A branch and bound algorithm to minimize the total tardiness for m-machine permutation flowshop problems, European Journal of Operational Research 174: 1-10, (2006).

DOI: 10.1016/j.ejor.2004.12.023

Google Scholar