An FPTAS for just-in-time scheduling of a flow shop manufacturing process with different service quality levels

Elalouf, Amir

RAIRO. Operations Research, Tome 55 (2021), pp. S727-S740

This paper addresses the problem of identifying a profit-maximizing schedule for jobs in a just-in-time production line, where the decision maker can adjust each job’s processing time, and thereby its quality level and the profit that can be gained from it. The system comprises two sequential machines with a transition period between them and a setup time after completion of each job on the second machine. We first construct an exact algorithm that maximizes the profit. Since this problem is NP-hard, we construct a fully polynomial time approximation scheme (FPTAS) to address it and evaluate its computational complexity.

Classification : 65D15, 05Exx, 68Rxx
Keywords: Flow shop scheduling, FPTAS, combinatorial optimization, dynamic programming

B. C. Choi and S. H. Yoon, Maximizing the weighted number of just-in-time jobs in flow shop scheduling. J. Sched. 10 (2007) 237–243. | MR | Zbl | DOI

R. L. Daniels and J. E. Carrillo, $\beta$-Robust scheduling for single-machine systems with uncertain processing times. IIE Trans. 29 (1997) 977–985. | DOI

A. Elalouf, E. Levner and H. Tang. An improved FPTAS for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem. J. Sched. 16 (2013) 429–435. | MR | Zbl | DOI

A. Elalouf and G. Wachtel, An alternative scheduling approach for improving emergency department performance. Int. J. Prod. Econ. 178 (2016) 65–71. | DOI

F. Ergun, R. Sinha and L. Zhang, An improved FPTAS for restricted shortest path. Inf. Process. Lett. 83 (2002) 287–291. | MR | Zbl | DOI

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co, New York, NY (1979). | Zbl

G. V. Gens and E. V. Levner, Fast approximation algorithm for job sequencing with deadlines. Discrete Appl. Math. 3 (1981), 313–318. | Zbl | DOI

R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5 (1979), 287–326. | MR | Zbl | DOI

I. Kacem, Fully polynomial-time approximation scheme for the weighted total tardiness minimization with a common due date. Discrete Appl. Math. 158 (2010) 1035–1040. | MR | Zbl | DOI

M. J. Mazzeo, Competition and service quality in the US airline industry. Rev. Ind. Organiz. 22 (2003) 275–296. | DOI

J. Miltenburg and G. Sinnamon, Scheduling mixed-model multi-level just-in-time production systems. Int. J. Prod. Res. 27 (2007) 1487–1509. | DOI

L. Pehrsson, A. H. C. Ng and J. Bernedixen, Automatic identification of constraints and improvement actions in production systems using multi-objective optimization and post-optimality analysis. J. Manuf. Syst. 39 (2016), 24–37. | DOI

Y. Perlman, A. Elalouf and E. Bodinger, Dynamic repair priority for a transfer line with a finite buffer. J. Manuf. Syst. 33 (2014) 16–26. | DOI

V. Polotski, J. Kenne and A. Gharbi, Optimal production scheduling for hybrid manufacturing–remanufacturing systems with setups. J. Manuf. Syst. 37 (2015) 703–714. | DOI

V. Toporkov, Application-level and job-flow scheduling: an approach for achieving quality of service in distributed computing. In: International Conference on Parallel Computing Technologies. Springer, Berlin Heidelberg (2009) 350–359.

G. J. Woeginger, When does a dynamic programming formulation guarantee the existence of an FPTAS? INFORMS J. Comput. 12 (2000) 57–74. | Zbl | DOI

H. Ye, W. Li and E. Miao, An effective heuristic for no-wait flow shop production to minimize makespan. J. Manuf. Syst. 40 (2016) 2–7. | DOI

L. Q. Zhang, L. F. Lu and C. T. Ng, The unbounded parallel-batch scheduling with rejection. J. Oper. Res. Soc. 63 (2012) 293–298. | DOI