Critical paths of non-permutation and permutation flow shop scheduling problems

Abstract: The literature on flow shop scheduling has extensively analyzed two classes of problems: permutation and non-permutation ones (PFS and NPFS). Most of the papers in this field have been just devoted on comparing the solutions obtained in both approaches. Our contribution consists of analyzing the structure of the critical paths determining the makespan of both kinds of schedules for the case of 2 jobs and m machines. We introduce a new characterization of the critical paths of PFS solutions as well as a decomposition procedure, yielding a representation of NPFS solutions as sequences of partial PFS ones. In structural comparisons we find cases in which NPFS solutions are dominated by PFS solutions. Numerical comparisons indicate that a wider dispersion of processing times improves the chances of obtaining optimal non-permutation schedules, in particular when this dispersion affects only a few machines.

How to cite this paper

 Rossit, D., Tohmé, F., Frutos, M., Safe, M & Vásquez, �. (2020). Critical paths of non-permutation and permutation flow shop scheduling problems.International Journal of Industrial Engineering Computations , 11(2), 281-298.

Refrences

Akers Jr, S. B. (1956). Letter to the editor—A graphical approach to production scheduling problems. Operations Research, 4(2), 244-245.
Benavides, A. J., & Ritt, M. (2016). Two simple and effective heuristics for minimizing the makespan in non-permutation flow shops. Computers & Operations Research, 66, 160-169.
Błażewicz, J., Ecker, K. H., Pesch, E., Schmidt, G., & Weglarz, J. (2007). Handbook on scheduling: from theory to applications. Springer Science & Business Media.
Blazewicz, J., Ecker, K. H., Pesch, E., Schmidt, G., & Weglarz, J. (2013). Scheduling computer and manufacturing processes. springer science & Business media.
Conway, R. W., Maxwell, W. L., & Miller, L. W. (2003). Theory of scheduling. Courier Corporation.
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische mathematik, 1(1), 269-271.
Fomin, F. V., & Kratsch, D. (2010). Exact exponential algorithms. Springer Science & Business Media.
Garey, M. R., Johnson, D. S., & Sethi. R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research. 1(2). 117-129.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287-326.
Johnson, S. M. (1954). Optimal two‐and three‐stage production schedules with setup times included. Naval Research Logistics (NRL), 1(1), 61-68.
Kelley Jr, J. E., & Walker, M. R. (1959, December). Critical-path planning and scheduling. In Papers presented at the December 1-3, 1959, eastern joint IRE-AIEE-ACM computer conference (pp. 160-173). ACM.
Kelley Jr, J. E. (1961). Critical-path planning and scheduling: Mathematical basis. Operations Research, 9(3), 296-320.
Kis, T., & Pesch, E. (2005). A review of exact solution methods for the non-preemptive multiprocessor flowshop problem. European Journal of Operational Research, 164(3), 592-608.
Li, S., & Tang, L. (2005). A tabu search algorithm based on new block properties and speed-up method for permutation flow-shop with finite intermediate storage. Journal of Intelligent Manufacturing, 16(4-5), 463-477.
Liao, C. J., Liao, L. M., & Tseng. C. T. (2006). A performance evaluation of permutation vs. non-permutation schedules in a flowshop. International Journal of Production Research. 44(20). 4297-4309.
Liao, L. M.. & Huang, C. J. (2010). Tabu search for non-permutation flowshop scheduling problem with minimizing total tardiness. Applied Mathematics and Computation, 217(2). 557-567.
Lin, S. W.. & Ying, K. C. (2009). Applying a hybrid simulated annealing and tabu search approach to non-permutation flowshop scheduling problems. International Journal of Production Research, 47(5). 1411-1424.
Nagarajan, V.. & Sviridenko, M. (2009). Tight bounds for permutation flow shop scheduling. Mathematics of Operations Research. 34(2). 417-427.
Nip, K., & Wang, Z. (2013, June). Combination of Two-Machine Flow Shop Scheduling and Shortest Path Problems. In COCOON (pp. 680-687).
Nip, K., Wang, Z., Nobibon, F. T., & Leus, R. (2015). A combination of flow shop scheduling and the shortest path problem. Journal of Combinatorial Optimization, 29(1), 36-52.
Pinedo, M. L. (2002). Scheduling: theory. algorithms. and systems. Springer Science & Business Media.
Potts, C. N., Shmoys, D. B., & Williamson, D. P. (1991). Permutation vs. non-permutation flow shop schedules. Operations Research Letters. 10(5). 281-284.
Rebaine, D. (2005). Flow shop vs. permutation shop with time delays. Computers & Industrial Engineering. 48(2). 357-362.
Rossi, A., & Lanzetta, M. (2013). Scheduling flow lines with buffers by ant colony digraph. Expert Systems with Applications, 40(9), 3328-3340.
Rossi, A., & Lanzetta, M. (2014). Native metaheuristics for non-permutation flowshop scheduling. Journal of Intelligent Manufacturing, 25(6), 1221-1233.
Rossit, D., Tohmé, F., Frutos, M., Bard, J., & Broz, D. (2016). A non-permutation flowshop scheduling problem with lot streaming: A Mathematical model. International Journal of Industrial Engineering Computations, 7(3), 507-516.
Rossit, D. A., Tohmé, F., & Frutos, M. (2018a). The non-permutation flow-shop scheduling problem: a literature review. Omega. 77, 143-153.
Rossit, D. A., Vásquez, Ó. C., Tohmé, F., Frutos, M., & Safe, M. D. (2018b). The dominance flow shop scheduling problem. Electronic Notes in Discrete Mathematics, 69, 21-28.
Rudek, R. (2011). Computational complexity and solution algorithms for flowshop scheduling problems with the learning effect. Computers & Industrial Engineering, 61(1), 20-31.
Shen, L., Gupta, J. N., & Buscher. U. (2014). Flow shop batching and scheduling with sequence-dependent setup times. Journal of Scheduling, 17(4), 353-370.
Taillard, E. (1993). Benchmarks for basic scheduling problems. European journal of operational research, 64(2), 278-285.
Tandon, M., Cummings, P. T., & LeVan, M. D. (1991). Flowshop sequencing with non-permutation schedules. Computers & chemical engineering, 15(8), 601-607.
Vahedi-Nouri, B., Fattahi, P., & Ramezanian, R. (2013). Minimizing total flow time for the non-permutation flow shop scheduling problem with learning effects and availability constraints. Journal of Manufacturing Systems, 32(1), 167-173.
Woeginger, G. J. (2003). Exact algorithms for NP-hard problems: A survey. Lecture Notes in Computer Science, 2570(2003), 185-207.
Xiao, Y., Yuan, Y., Zhang, R. Q., & Konak. A. (2015). Non-permutation flow shop scheduling with order acceptance and weighted tardiness. Applied Mathematics and Computation, 270, 312-333.
Ying, K. C., & Lin, S. W. (2007). Multi-heuristic desirability ant colony system heuristic for non-permutation flowshop scheduling problems. The International Journal of Advanced Manufacturing Technology, 33(7-8), 793-802.
Ying, K. C. (2008). Solving non-permutation flowshop scheduling problems by an effective iterated greedy heuristic. The International Journal of Advanced Manufacturing Technology, 38(3-4), 348-354.
Ying, K. C.. Gupta, J. N., Lin. S. W., & Lee, Z. J. (2010). Permutation and non-permutation schedules for the flowline manufacturing cell with sequence dependent family setups. International Journal of Production Research, 48(8), 2169-2184.
Ziaee, M. (2013). General flowshop scheduling problem with the sequence dependent setup times: A heuristic approach. Information Sciences, 251, 126-135.