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 91
- Downloads 0
An Evaluation of the Implementation of Practice Teaching Program for Prospective Teachers at Ganesha University of Education Based on CIPP-Forward Chaining
The recognition of teacher status is very high and this is followed by a requirement of a high competence level that a teacher has to have that the existence of teachers has to gain a serious attention, including a...
Diagrammatic Language for Artificial Intelligence: Representation of Things that Flow
This paper utilizes a diagrammatic language for expressing certain philosophical notions, such as possible worlds, beliefs, and propositions. The focus is on a diagrammatic representation that depicts “things” to s...
Contradiction Resolution of Competitive and Input Neurons to Improve Prediction and Visualization Performance
In this paper, we propose a new type of informationtheoretic method to resolve the contradiction observed in competitive and input neurons. For competitive neurons, contradiction between self-evaluation (individuality) a...
Estimation of Protein Content in Rice Crop and Nitrogen Content in Rice Leaves Through Regression Analysis with NDVI Derived from Camera Mounted Radio-Control Helicopter
Estimation of protein content in rice crop and nitrogen content in rice leaves through regression analysis with Normalized Difference Vegetation Index: NDVI derived from camera mounted radio-control helicopter is p...
Driver’s Awareness and Lane Changing Maneuver in Traffic Flow based on Cellular Automaton Model
Effect of driver’s awareness (e.g., to estimate the speed and arrival time of another vehicle) on the lane changing maneuver is discussed. “Scope awareness” is defined as the visibility which is required for the dr...