×

Upper and lower bounds for the permutation flowshop scheduling problem with minimal time lags. (English) Zbl 1310.90067

Summary: In this paper, we consider the problem of scheduling \(n\) jobs in an \(m\)-machine permutation flowshop with minimal time lags between consecutive operations of each job. The processing order of jobs is to be the same for each machine. The time lag is defined as the waiting time between two consecutive operations of each job. Upper bounds for the problem are provided by applying heuristic procedures based on known and new rules. Lower bounds based on Moore’s algorithm and logic-based Benders decomposition are developed. For the last one, we define a long time horizon on the last machine divided into many segments of time. We combine a mixed integer linear programming to allocate jobs to time segments and scheduled using the constraint programming. Then, computational results are reported.

MSC:

90B85 Continuous location
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chu, C., Proth, J.M.: Single machine scheduling with chain structured precedence constraints and separation time windows. IEEE Trans. Robot. Autom. 12, 835-844 (1996) · doi:10.1109/70.544767
[2] Coban, E., Hooker, J.N.: Single-facility scheduling over long time horizons by logic-based benders decomposition. In: Proceedings of CPAIOR, pp. 87-91 (2010) · Zbl 1285.68154
[3] Croce, F.D., Gupta, G.N.D., Tadei, R.: Minimizing tardy jobs in a flowshop with common due date. Eur. J. Oper. Res. 120, 375-81 (2000) · Zbl 0949.90040 · doi:10.1016/S0377-2217(99)00164-2
[4] Deppner, F.: Ordonnancement d’atelier avec contraintes temporelles entre operations. Ph.D. Thesis, Institut National Polytechnique de Lorraine (in French) (2004) · Zbl 1175.90190
[5] Dhouib, E., Teghem, J., Loukil, T.: Minimizing the number of tardy jobs in a permutation flowshop scheduling problem with setup times and time lags constraints. J. Math. Model. Algorith. Oper. Res. 12, 85-99 (2013) · Zbl 1311.90045
[6] Fondrevelle, J., Oulamara, A., Portmann, M.C.: Permutation flowshop scheduling problems with maximal and minimal time lags. Comput. Oper. Res. 33, 1540-1556 (2006) · Zbl 1091.90081 · doi:10.1016/j.cor.2004.11.006
[7] Ghassemi, T.F., Olfat, L.: A set of algorithms for solving the generalized tardiness flowshop problems. J. Ind. Syst. Eng. 4, 156-166 (2010)
[8] Graham, R., Lawler, E., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287-326 (1979) · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X
[9] Hariri, A.M.A., Potts, C.N.: A branch and bound algorithm to minimize the number of late jobs in a permutation flowshop. Eur. J. Oper. Res. 38, 228-237 (1989) · Zbl 0674.90048 · doi:10.1016/0377-2217(89)90108-2
[10] Harjunkoski, I., Grossmann, I.E.: Decomposition techniques for multistage scheduling problems using mixed-integer and constraint programming methods. Comput. Chem. Eng. 26, 1533-1552 (2002) · doi:10.1016/S0098-1354(02)00100-X
[11] Hooker, JN; Yan, H.; Saraswat, V. (ed.); Hentenryck, P. (ed.), Logic circuit verification by Benders decomposition, 267-288 (1995), Cambridge
[12] Hooker, J.N.: Logic-based Benders decomposition. Carnegie-Mellon University, Technical report (1995) · Zbl 1023.90082
[13] Hooker, JN; Wallace, M. (ed.), A hybrid method for planning and scheduling, No. 3258, 305-316 (2004), Berlin · Zbl 1152.90445
[14] Hooker, JN; Beek, P. (ed.), Planning and scheduling to minimize tardiness, No. 3709, 314-327 (2005), Berlin · Zbl 1153.90423
[15] Hooker, J.N.: Planning and scheduling by logic-based benders decomposition. Oper. Res. 55, 588-602 (2007) · Zbl 1167.90512 · doi:10.1287/opre.1060.0371
[16] Jain, V., Grossmann, I.E.: Algorithms for hybrid milp/cp models for a class of optimization problems. INFORMS J. Comput. 13, 258-276 (2001) · Zbl 1238.90106 · doi:10.1287/ijoc.13.4.258.9733
[17] Lenstra, J.K., Rinnooy Kan, A.H.G., Brucker, P.: Complexity of machine scheduling problems. Ann. Discrete Math. 1, 343-362 (1977) · doi:10.1016/S0167-5060(08)70743-X
[18] Lodree, E., Jang, W., Klein, C.M.A.: New rule for minimizing the nuımber of tardy jobs in dynamic flowshops. Eur. J. Oper. Res. 159, 258-263 (2004) · Zbl 1065.90039 · doi:10.1016/S0377-2217(03)00404-1
[19] Moore, J.M.: An n job one machine algorithm for minimizing the number of late jobs. Manage. Sci. 15, 102-109 (1968) · Zbl 0164.20002 · doi:10.1287/mnsc.15.1.102
[20] Ruiz-Torres, A.J., Ablanedo-Rosasb, J.H., Johnny, C.H.: Minimizing the number of tardy jobs in the flow shop problem with operation and resource flexibility. Comput. Oper. Res. 37, 282-291 (2010) · Zbl 1175.90190 · doi:10.1016/j.cor.2009.04.018
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.