Mixed-integer programming models for flowshop scheduling problems minimizing the total earliness and tardiness. (English) Zbl 1355.90028
Ríos-Mercado, Roger Z. (ed.) et al., Just-in-time systems. New York, NY: Springer (ISBN 978-1-4614-1122-2/hbk; 978-1-4614-1123-9/ebook). Springer Optimization and Its Applications 60, 91-105 (2012).
Summary: Scheduling problems involving both earliness and tardiness costs have received significant attention in recent years. This type of problem became important with the advent of the just-in-time (JIT) concept, where early or tardy deliveries are highly discouraged. In this work we examine the flowshop scheduling problem with no storage constraints and with blocking in-process. In this latter environment, there are no buffers between successive machines; therefore, intermediate queues of jobs waiting in the system for their next operations are not allowed. Performance is measured by the minimization of the sum of earliness and tardiness of the jobs. Mixed-integer models that represent these scheduling flowshop problems are presented. The models are evaluated and compared in several problems using commercial known software.
For the entire collection see [Zbl 1231.90005].
For the entire collection see [Zbl 1231.90005].
Software:
AMPLReferences:
| [1] | Biskup, D.; Feldmann, M., Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates, Computers & Operations Research, 28, 787-801 (2001) · Zbl 1003.90020 · doi:10.1016/S0305-0548(00)00008-3 |
| [2] | Brandimarte, P.: Neighbourhood search-based optimization algorithms for production scheduling: a survey. Running Series - Designing Production Order Scheduling Tools 5(2) (1992) |
| [3] | Dudek, RA; Panwalkar, SS; Smith, ML, The lessons of flowshop scheduling research, Operations Research, 40, 7-13 (1992) · Zbl 0825.90554 · doi:10.1287/opre.40.1.7 |
| [4] | Grabowski, J.; Pempera, J., The permutation flow shop problem with blocking: A Tabu Search approach, Omega, 35, 302-311 (2007) · doi:10.1016/j.omega.2005.07.004 |
| [5] | Hall, NG; Sriskandarajah, C., A survey of machine scheduling problems with blocking and no-wait in process, Operations Research, 44, 510-525 (1996) · Zbl 0864.90060 · doi:10.1287/opre.44.3.510 |
| [6] | Kanet, JJ; Sridharan, V., Scheduling with inserted idle time: problem taxonomy and literature review, Operations Research, 48, 99-110 (2000) · doi:10.1287/opre.48.1.99.12447 |
| [7] | Kim, YD, Minimizing total tardiness in permutation flowshops, European Journal of Operational Research, 85, 541-555 (1995) · Zbl 0912.90174 · doi:10.1016/0377-2217(94)00029-C |
| [8] | Leisten, R., Flowshop sequencing with limited buffer storage, International Journal of Production Research, 28, 2085-2100 (1990) · Zbl 0707.90054 · doi:10.1080/00207549008942855 |
| [9] | Liao, CJ; You, CT, An improved formulation for the job-shop scheduling problem, Journal of the Operational Research Society, 43, 1047-1054 (1992) · Zbl 0775.90236 |
| [10] | Manne, AS, On the job-shop scheduling problem, Operations Research, 8, 219-223 (1960) · doi:10.1287/opre.8.2.219 |
| [11] | Pan, CH, A study of integer programming formulations for scheduling problems, International Journal of Systems Science, 28, 33-41 (1997) · Zbl 0873.90054 · doi:10.1080/00207729708929360 |
| [12] | Potts, CN; van Wassenhove, LN, A decomposition algorithm for the single machine total tardiness problem, Operations Research Letters, 1, 177-181 (1982) · Zbl 0508.90045 · doi:10.1016/0167-6377(82)90035-9 |
| [13] | Reklaitis, GV, Review of scheduling of process operations, AIChE Symposium Series, 78, 119-133 (1982) |
| [14] | Ronconi, DP, A contribution to the study of the flowshop problem minimizing the total tardiness (1997), Dissertation (in portuguese), UNICAMP, Campinas, Brazil: Ph.D, Dissertation (in portuguese), UNICAMP, Campinas, Brazil |
| [15] | Sen, T.; Gupta, SK, A state-of-art survey of static scheduling research involving due dates, Omega, 12, 63-76 (1984) · doi:10.1016/0305-0483(84)90011-2 |
| [16] | Sethi, SP; Sriskandarajah, C.; Sorger, G.; Blazewicz, J.; Kubiak, W., Sequencing of parts and robot moves in a robotic cell, International Journal of Flexible Manufacturing Systems, 4, 331-358 (1992) · doi:10.1007/BF01324886 |
| [17] | Stafford, EF, On the development of a mixed-integer linear programming model for the flowshop sequencing problem, Journal of the Operational Research Society, 39, 1163-1174 (1988) · Zbl 0663.90046 |
| [18] | Stafford, E. F.; Tseng, F. T.,J. N.; Gupta, J. N.D., Comparative evaluation of MILP flowshop models, Journal of the Operational Research Society, 5, 88-101 (2005) · Zbl 1122.90359 |
| [19] | Taillard, E., Benchmarks for basic scheduling problems, European Journal of Operational Research, 64, 278-285 (1993) · Zbl 0769.90052 · doi:10.1016/0377-2217(93)90182-M |
| [20] | Wagner, HM, An integer linear-programming model for machine scheduling, Naval Research Logistic, 6, 131-140 (1959) · doi:10.1002/nav.3800060205 |
| [21] | Wilson, JM, Alternative formulations of a flow-shop scheduling problem, Journal of the Operational Research Society, 40, 395-399 (1989) · Zbl 0667.90050 |
| [22] | Zhu, Z.; Heady, RB, Minimizing the sum of earliness/tardiness in multimachine scheduling: a mixed integer programming approach, Computers & Industrial Engineering, 38, 297-305 (2000) · doi:10.1016/S0360-8352(00)00048-6 |
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.
