A structural property of flow shop sequencing with separated machine setup times. (Portuguese. English summary) Zbl 1176.90233
Summary: This paper deals with the permutation flow shop scheduling problem with separated machine setup times. As a result of an investigation on the problem characteristics a structural property is introduced. Such a property provides an upper bound on the idle time of the machines between the setup task and the job processing. As an application of this property, the original scheduling problem with the makespan criterion can be heuristically solved by an analogy with the asymmetric traveling salesman problem.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Allahverdi A., Job lateness in flowshops with setup and removal times separated, Journal of the Operational Research Society 49 pp 1001– (1998) · Zbl 1140.90386 · doi:10.1057/palgrave.jors.2600583 |
| [2] | Bagga P.C., Two-machine flowshop with separated sequence-independent setup times: mean completion time criterion, Indian Journal of Management and Systems 2 pp 47– (1986) |
| [3] | Bagchi T.P., A review of TSP based approaches for flowshop scheduling, European Journal of Operational Research 169 pp 816– (2006) · Zbl 1079.90048 · doi:10.1016/j.ejor.2004.06.040 |
| [4] | Cao J., flow shop scheduling in serial multi-product processes with transfer and setup times, International Journal of Production Research 30 pp 1819– (1992) · doi:10.1080/00207549208948124 |
| [5] | Cheng T.C.E., A review of flowshop scheduling research with setup times, Production and Operations Management 9 pp 262– (2000) · doi:10.1111/j.1937-5956.2000.tb00137.x |
| [6] | Corwin B.D., Two-machine flowshop scheduling problems with sequence dependent setup times: a dynamic programming approach, Naval Research Logistics Quarterly 21 pp 515– (1974) · Zbl 0289.90026 · doi:10.1002/nav.3800210311 |
| [7] | Das S.R., A savings index heuristic algorithm for flowshop scheduling with sequence dependent set-up times, Journal of the Operational Research Society 46 pp 1365– (1995) · Zbl 0858.90074 · doi:10.1057/jors.1995.184 |
| [8] | French S., Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop (1982) · Zbl 0479.90037 |
| [9] | Framinan J.M., A review and classification of heuristics for permutation flow-shop scheduling with makespan objective, Journal of the Operational Research Society 55 pp 1243– (2004) · Zbl 1088.90022 · doi:10.1057/palgrave.jors.2601784 |
| [10] | Garey M.R., The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research 1 pp 117– (1976) · Zbl 0396.90041 · doi:10.1287/moor.1.2.117 |
| [11] | Gupta J.N.D., Travelling salesman problem: a survey of theoretical developments and applications, Opsearch (India) 5 pp 181– (1968) |
| [12] | Gupta J.N.D., Economic aspects of scheduling theory (1969) |
| [13] | Gupta J.N.D., A search algorithm for the generalized scheduling problem, Computers & Operations Research 2 pp 83– (1975) · doi:10.1016/0305-0548(75)90011-8 |
| [14] | Gupta J.N.D., Approximate schedules for the two-machine flow-shop with sequence dependent setup times, Indian Journal of Management and Systems 1 pp 6– (1985) |
| [15] | Gupta J.N.D., The two-machine sequence dependent flowshop scheduling problem, European Journal of Operational Research 24 pp 439– (1986) · Zbl 0601.90075 · doi:10.1016/0377-2217(86)90037-8 |
| [16] | Gupta J.N.D., Flowshop scheduling research after five decades, European Journal of Operational Research 169 pp 699– (2006) · Zbl 1079.90001 · doi:10.1016/j.ejor.2005.02.001 |
| [17] | Gupta J.N.D., Two-stage no-wait scheduling models with setup and removal times, Computers & Operations Research 24 pp 1025– (1997) · Zbl 0889.90086 · doi:10.1016/S0305-0548(97)00018-X |
| [18] | Hejazi S.R., Flowshop-scheduling problems with makespan criterion: a review, International Journal of Production Research 43 pp 2895– (2005) · Zbl 1068.90059 · doi:10.1080/0020754050056417 |
| [19] | Johnson S., Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly 1 pp 61– (1954) · Zbl 1349.90359 · doi:10.1002/nav.3800010110 |
| [20] | Khurana K., Scheduling of job-block with deadline in n X 2 flowshop problem with separated setup times, Indian Journal of Pure Applied Mathematics 16 pp 213– (1985) · Zbl 0568.90040 |
| [21] | Moccellin J.V., A new heuristic method for the permutation flow shop scheduling problem, Journal of the Operational Research Society 46 pp 883– (1995) · Zbl 0832.90057 · doi:10.1057/jors.1995.119 |
| [22] | Mood A.M., Introduction to the Theory of Statistics (1974) · Zbl 0277.62002 |
| [23] | Park T., Analysis of heuristics for job sequencing in manufacturing flow line work-cells, Computers & Industrial Engineering 20 pp 129– (1991) · doi:10.1016/0360-8352(91)90048-B |
| [24] | Pinedo M., Scheduling: Theory, Algorithms, and Systems (1995) · Zbl 1145.90393 |
| [25] | Rajendran C., Heuristics for scheduling in a flowshop with setup, processing and removal times separated, Production Planning & Control 8 pp 568– (1997) · doi:10.1080/095372897234902 |
| [26] | Rios-Mercado R.Z., The flowshop scheduling polyhedron with setup times (1996) |
| [27] | Rios-Mercado R.Z., Heuristics for the flow line problem with setup costs, European Journal of Operational Research 110 pp 76– (1998) · Zbl 0948.90070 · doi:10.1016/S0377-2217(97)00213-0 |
| [28] | Rios-Mercado R.Z., A branch-and-bound algorithm for flowshop scheduling with setup times, IEE Transactions 31 pp 721– (1999) · doi:10.1080/07408179908969871 |
| [29] | Rios-Mercado R.Z., An enhanced TSP-based heuristic for makespan minimization in a flowshop with setup times, Journal of Heuristics 5 pp 53– (1999) · Zbl 0948.90071 · doi:10.1023/A:1009691028143 |
| [30] | Simons Jr. J.V., Heuristics in flow shop scheduling with sequence dependent setup times, Omega 20 pp 215– (1992) · doi:10.1016/0305-0483(92)90075-I |
| [31] | Srikar B.N., A MILP model for the n-job, m-stage flowshop, with sequence dependent setup times, International Journal of Production Research 24 pp 1459– (1986) · Zbl 0605.90066 · doi:10.1080/00207548608919815 |
| [32] | Stafford E.F., On the Srikar-Ghosh MILP model for the N X M SDST flowshop problem, International Journal of Production Research 28 pp 1817– (1990) · doi:10.1080/00207549008942836 |
| [33] | Stinson J.P., A heuristic programming procedure for sequencing the static flowshop, International Journal of Production Research 20 pp 753– (1982) · doi:10.1080/00207548208947802 |
| [34] | Yoshida T., Optimal two-stage production scheduling with setup times separated, AIEE Transactions 11 pp 261– (1979) · doi:10.1080/05695557908974469 |
| [35] | Weng M.X., Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective, International Journal of Production Economics 70 pp 215– (2001) · doi:10.1016/S0925-5273(00)00066-9 |
| [36] | Widmer M., A new heuristic method for the flow shop sequencing problem, European Journal of Operational Research 41 pp 186– (1989) · Zbl 0671.90040 · doi:10.1016/0377-2217(89)90383-4 |
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.
