Hybrid Metaheuristics for the Unrelated Parallel Machine Scheduling to Minimize Makespan and Maximum Just-in-Time Deviations
Journal Title: International Journal of Advanced Research in Artificial Intelligence(IJARAI) - Year 2012, Vol 1, Issue 3
Abstract
This paper studies the unrelated parallel machine scheduling problem with three minimization objectives – makespan, maximum earliness, and maximum tardiness (MET-UPMSP). The last two objectives combined are related to just-in-time (JIT) performance of a solution. Three hybrid algorithms are presented to solve the MET-UPMSP: reactive GRASP with path relinking, dual-archived memetic algorithm (DAMA), and SPEA2. In order to improve the solution quality, min-max matching is included in the decoding scheme for each algorithm. An experiment is conducted to evaluate the performance of the three algorithms, using 100 (jobs) x 3 (machines) and 200 x 5 problem instances with three combinations of two due date factors – tight and range. The numerical results indicate that DAMA performs best and GRASP performs second for most problem instances in three performance metrics: HVR, GD, and Spread. The experimental results also show that incorporating min-max matching into decoding scheme significantly improves the solution quality for the two population-based algorithms. It is worth noting that the solutions produced by DAMA with matching decoding can be used as benchmark to evaluate the performance of other algorithms.
Authors and Affiliations
Chiuh-Cheng Chyu, Wei-Shung Chang
Keywords
Related Articles
- EP ID EP140413
- DOI -
- Views 114
- Downloads 0
Secure Copier Which Allows Reuse Copied Documents with Sorting Capability in Accordance with Document Types
Secure copy machine which allows reuse copied documents with sorting capability in accordance with the document types. Through experiments with a variety of document types, it is found that copied documents can be shared...
A Multistage Feature Selection Model for Document Classification Using Information Gain and Rough Set
Huge number of documents are increasing rapidly, therefore, to organize it in digitized form text categorization becomes an challenging issue. A major issue for text categorization is its large number of features....
A Directional Audible Sound System using Ultrasonic Transducers
In general the audible sound has the characteristics of spreading, however the ultrasound is directional. This study used amplitude-modulating technique for an array of 8 ultrasonic transducers to produce direction...
Multifidus Muscle Volume Estimation Based on Three Dimensional Wavelet Multi Resolution Analysis: MRA with Buttocks Computer-Tomography: CT Images
Multi-Resolution Analysis:. MRA based edge detection algorithm is proposed for estimation of volume of multifidus muscle in the Computer Tomography: CT scanned image The volume of multifidus muscle would be a good measur...
New Hybrid (SVMs -CSOA) Architecture for classifying Electrocardiograms Signals
a medical test that provides diagnostic relevant information of the heart activity is obtained by means of an ElectroCardioGram (ECG). Many heart diseases can be found by analyzing ECG because this method with mora...