Back to Search
Start Over
Minimizing the makespan in a two-machine cross-docking flow shop problem
- Source :
- European Journal of Operational Research. 193:59-72
- Publication Year :
- 2009
- Publisher :
- Elsevier BV, 2009.
-
Abstract
- This paper studies a two-machine cross-docking flow shop scheduling problem in which a job at the second machine can be processed only after the processing of some jobs at the first machine has been completed. The objective is to minimize the makespan. We first show that the problem is strongly NP-hard. Some polynomially solvable special cases are provided. We then develop a polynomial approximation algorithm with an error-bound analysis. A branch-and-bound algorithm is also constructed. Computational results show that the branch-and-bound algorithm can optimally solve problems with up to 60 jobs within a reasonable amount of time.
- Subjects :
- Mathematical optimization
Information Systems and Management
business.product_category
General Computer Science
Job shop scheduling
Approximation algorithm
Flow shop scheduling
Management Science and Operations Research
Industrial and Manufacturing Engineering
Scheduling (computing)
Paper machine
Approximation error
Modeling and Simulation
Johnson's rule
Cross-docking
business
Algorithm
Computer Science::Distributed, Parallel, and Cluster Computing
Mathematics
Subjects
Details
- ISSN :
- 03772217
- Volume :
- 193
- Database :
- OpenAIRE
- Journal :
- European Journal of Operational Research
- Accession number :
- edsair.doi...........fd83475b4e20656dc7a6af0b0949baaa