Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 8

Proceedings of the 2016 Federated Conference on Computer Science and Information Systems

Minimizing Total Completion Time in Flowshop with Availability Constraint on the First Machine

,

DOI: http://dx.doi.org/10.15439/2016F447

Citation: Proceedings of the 2016 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 8, pages 627–635 ()

Full text

Abstract. We study the problem of minimizing total completion time in 2-stage flowshop with availability constraint. This problem is NP-hard in the strong sense even if both machines are always available. With availability constraint, although a bulk of research papers have studied the makespan minimization problem, there is no research done on the total completion time minimization. This paper is the first attempt to tackle this problem. We focus on the case that there is a single unavailable interval on the first machine only. We show that several special cases can be solved optimally or approximated within a constant factor. For the general case, we develop some lower bounds and dominance rules. Then we design and implement a branch and bound algorithm. We investigate the effectiveness of different lower bounds and the dominance rules by computational experiments. We also study how the start time and the duration of the unavailable interval affects the efficiency of the branch and bound algorithm.

References

  1. Akkan, C. and S. Karabati, The two-machine flowshop total completion time problem: Improved lower bounds and a branch-and-bound algorithm, European Journal of Operational Research, 159, 420-429, 2004, http://dx.doi.org/10.1016/S0377-2217(03)00415-6.
  2. Cadambi, B. W. and Y. S. Sathe, Two-machine flowshop scheduling to minimise mean flow time, Opsearch, 30, 35-41,1993.
  3. Conway, R. W., W. L. Maxwell, and L. W. Miller, Theory of Scheduling. Addison-Wesley, Reading, MA, 1967.
  4. Della Croce, F., M. Ghirardi, and R. Tadei, An improved branch-and- bound algorithm for the two machine total completion time flow shop problem, European Journal of Operational Research, 139, 293-301, 2002, http://dx.doi.org/10.1016/S0377-2217(01)00374-5.
  5. Della Croce, F., V. Narayan, and R. Tadei, The two-machine total completion time flow shop problem, European Journal of Operational Research, 90, 227-237, 1996, http://dx.doi.org/10.1016/0377-2217(95)00351-7.
  6. Garey, M. R., D. S. Johnson, and R. Sethi, The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research, 13, 330-348, 1976, http://dx.doi.org/10.1287/moor.1.2.117.
  7. T. Gonzalez and S. Sahni, Flowshop and jobshop schedules: Complexity and approximation. Operations Research 26, 36-52, 1978,http://dx.doi.org/10.1287/opre.26.1.36.
  8. J.N.D. Gupta and R.A.Dudek, Optimality criteria for flowshop schedules, AIIE Trans, 3, 199-205, 1971, http://dx.doi.org/10.1080/05695557108974807.
  9. H. Hoogeveen and T. Kawaguchi, Minimizing total completion time in a two-machine flowshop: Analysis of special cases, Mathematics of Operations Research, Vol. 24 Issue 4, 887-910, 1999, http://dx.doi.org/10.1287/moor.24.4.887.
  10. Hoogeveen, J. A. and S. L. Van de Velde, Stronger Lagrangian bounds by use of slack variables: applications to machine scheduling problems, Mathematical Programming, 70, 173-190, 1995, http://dx.doi.org/10.1007/BF01585935.
  11. Hoogeveen, J. A. and S. L. Van de Velde, Scheduling by positional completion times: Analysis of a two-stage flow shop problem with a batching machine, Mathematical Programming, 82, 273-289, 1998, http://dx.doi.org/10.1007/BF01585876.
  12. Hoogeveen, J. A., L. van Norden and S. L. Van de Velde, Lower bounds for minimizing total completion time in a two-machine flow shop, Journal of Scheduling, 9: 559-568, 2006, http://dx.doi.org/10.1007/s10951-006-8789-x.
  13. Ignall, E., and L. E. Scharge, Application of the branch and bound technique to some flow-shop problems, Operations Research, 13, 400-412, 1965, http://dx.doi.org/10.1287/opre.13.3.400.
  14. Kohler, W. H. and K. Steiglitz, Exact, approximate and guaranteed accuracy algorithms for the flowshop problem n/2/F/F, Journal ACM, 22, 106-114, 1975, http://dx.doi.org/10.1145/321864.321872.
  15. W. Kubiak, J.Blazewicz, P. Formanowicz, J. Breit and G. Schmidt, Two-machine flow shops with limited machine availability, European Journal of Operational Research Volume 136, Issue 3, pp. 528-540, 2002, http://dx.doi.org/10.1016/S0377-2217(01)00083-2.
  16. C.-Y. Lee, Machine scheduling with an availability constraints, Journal of Global Optimization, 9, pp. 363-382, 1996, http://dx.doi.org/10.1007/BF00121681.
  17. C.-Y. Lee, Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint, Operations Research Letters, 20, pp. 129-139, 1997, http://dx.doi.org/10.1016/S0167-6377(96)00041-7
  18. C. Y. Lee, L. Lei and M. Pinedo, Current trends in deterministic scheduling, Annals of Operations Research, 70(0): 1-41, 1997.
  19. C. Y. Lee, Two-machine flowshop scheduling with availability constraints, European Journal of Operational Research, 114, pp. 420-429, 1999, http://dx.doi.org/10.1016/S0377-2217(97)00452-9
  20. Ma, Y., C. Chu and C. Zuo, A survey of scheduling with deterministic machine availability constraints, Computers & Industrial Engineering, 58(2), pp. 199-211, 2010, http://dx.doi.org/10.1016/j.cie.2009.04.014
  21. E. Sanlaville and G. Schmidt, Machine scheduling with availability constraints, Acta Informatica, 35, pp. 795-811, 1998.
  22. G. Schmidt. Scheduling with limited machine availability, Euro- pean Journal of Operational Research, 121(1), pp. 1-15, 2000, http://dx.doi.org/10.1016/S0377-2217(98)00367-1
  23. Van de Velde, S. L, Minimizing the sum of the job completion times in the two-machine flow shop by Lagrangian relaxation, Annals of Operations Research, 26, 257 - 268, 1990.