Back to Search
Start Over
A Decomposition-Based Two-Stage Optimization Algorithm for Single Machine Scheduling Problems with Deteriorating Jobs
- Source :
- Mathematical Problems in Engineering, Vol 2015 (2015)
- Publication Year :
- 2015
- Publisher :
- Hindawi Limited, 2015.
-
Abstract
- This paper studies a production scheduling problem with deteriorating jobs, which frequently arises in contemporary manufacturing environments. The objective is to find an optimal sequence of the set of jobs to minimize the total weighted tardiness, which is an indicator of service quality. The problem belongs to the class of NP-hard. When the number of jobs increases, the computational time required by an optimization algorithm to solve the problem will increase exponentially. To tackle large-scale problems efficiently, a two-stage method is presented in this paper. We partition the set of jobs into a few subsets by applying a neural network approach and thereby transform the large-scale problem into a series of small-scale problems. Then, we employ an improved metaheuristic algorithm (called GTS) which combines genetic algorithm with tabu search to find the solution for each subproblem. Finally, we integrate the obtained sequences for each subset of jobs and produce the final complete solution by enumeration. A fair comparison has been made between the two-stage method and the GTS without decomposition, and the experimental results show that the solution quality of the two-stage method is much better than that of GTS for large-scale problems.
- Subjects :
- Sequence
Mathematical optimization
Single-machine scheduling
Article Subject
Artificial neural network
General Mathematics
Tardiness
lcsh:Mathematics
General Engineering
lcsh:QA1-939
Tabu search
Set (abstract data type)
lcsh:TA1-2040
Genetic algorithm
lcsh:Engineering (General). Civil engineering (General)
Algorithm
Metaheuristic
Mathematics
Subjects
Details
- Language :
- English
- ISSN :
- 15635147
- Volume :
- 2015
- Database :
- OpenAIRE
- Journal :
- Mathematical Problems in Engineering
- Accession number :
- edsair.doi.dedup.....df2aff58762d24beda6c4a1ac8ed374c