×

Scheduling flexible manufacturing cells using tabu search. (English) Zbl 1198.90206

Summary: Scheduling is an important aspect in the overall control of a flexible manufacturing system. The research presented focuses on production scheduling of jobs within a flexible manufacturing cell (FMC)-one type of flexible manufacturing system. Due to the complexity of the FMC scheduling problem, a 0-1 mixed-integer linear programming (MILP) model is formulated for \(M\) machines and \(N\) jobs with alternative routings. Although small instances of the problem can be solved optimally with MILP models, a two-stage Tabu Search \((TS^{2})\) algorithm that minimises the manufacturing makespan \((MS)\) is proposed to solve medium-to-large-scale problems more efficiently. During Stage I (construction phase), two heuristics are utilised to generate an initial feasible sequence and an initial \(MS\) solution. In Stage II (improvement phase), the acquired initial solutions from Stage I are combined with a Tabu Search meta-heuristic procedure that provides improved \(MS\) solutions. The \(TS^{2}\) algorithm provides tremendous savings in computational time for medium/large-sized multi-machine FMC problems.

MSC:

90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming

Software:

lpSolve
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1080/09511920500399474
[2] Berkelaar M, LPSolve IDE version 5.1.0.2 software (2004)
[3] DOI: 10.1016/0377-2217(88)90192-0 · Zbl 0652.90058
[4] DOI: 10.1023/B:JIMS.0000010077.27141.be
[5] DOI: 10.1016/j.rcim.2005.08.001
[6] French S, Sequencing and scheduling: an introduction to the mathematics of the job-shop (1982) · Zbl 0479.90037
[7] DOI: 10.1016/S0736-5845(02)00061-3
[8] Glover F, ORSA Journal of Computing 1 pp 190– (1989)
[9] Ibarra OH, Journal of the Association for Computing Machinery 24 pp 280– (1977)
[10] DOI: 10.1007/s00170-003-1933-2
[11] DOI: 10.1243/095440503322617216
[12] DOI: 10.1080/00207549608904925 · Zbl 0926.90030
[13] DOI: 10.1016/S0377-2217(96)00055-0 · Zbl 0917.90171
[14] Logendran R, Journal of the Operational Research Society 48 pp 264– (1997) · Zbl 0890.90086
[15] DOI: 10.1080/00207540150504403 · Zbl 1060.90647
[16] Pitts RA, A mathematical programming approach for routing and scheduling flexible manufacturing cells Thesis (PhD) (2006)
[17] Pitts, RA and Ventura, J. 2006. Two-stage algorithm for routing and scheduling flexible manufacturing cells.In:Proceedings of the IIE Annual Conference & Exposition. 2006, Orlando, Florida. USA, 6 pp. (cd-rom)
[18] DOI: 10.1016/S0377-2217(02)00795-6 · Zbl 1099.90023
[19] DOI: 10.1016/S0377-2217(97)00433-5 · Zbl 0933.90030
[20] DOI: 10.1016/j.rcim.2003.09.001
[21] DOI: 10.1016/0278-6125(93)90322-K
[22] DOI: 10.1080/0951192031000077870
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.