Optimally rescheduling jobs with a Last-In-First-Out buffer

Journal of Scheduling - 2021
Gaia Nicosia1, Andrea Pacifici2, Ulrich Pferschy3, Julia Resch3, Giovanni Righini4
1Dipartimento di Ingegneria, Università Roma Tre, Via della Vasca Navale 79, 00146, Rome, Italy
2Dipartimento di Ingegneria Civile e Ingegneria Informatica, Università di Roma "Tor Vergata", Via del Politecnico 1, 00133, Rome, Italy
3Department of Operations and Information Systems, University of Graz, Universitaetsstrasse 15, 8010, Graz, Austria
4Dipartimento di Informatica, Università degli Studi di Milano, Via Celoria 18, 20100, Milan, Italy

Tóm tắt

AbstractThis paper considers single-machine scheduling problems in which a given solution, i.e., an ordered set of jobs, has to be improved as much as possible by re-sequencing the jobs. The need for rescheduling may arise in different contexts, e.g., due to changes in the job data or because of the local objective in a stage of a supply chain that is not aligned with the given sequence. A common production setting entails the movement of jobs (or parts) on a conveyor. This is reflected in our model by facilitating the re-sequencing of jobs via a buffer of limited capacity accessible by a LIFO policy. We consider the classical objective functions of total weighted completion time, maximum lateness and (weighted) number of late jobs and study their complexity. For three of these problems, we present strictly polynomial-time dynamic programming algorithms, while for the case of minimizing the weighted number of late jobs NP-hardness is proven and a pseudo-polynomial algorithm is given.

Từ khóa


Tài liệu tham khảo

Agnetis, A., Detti, P., Meloni, C., & Pacciarelli, D. (2001). Coordination between two stages of a supply chain. Annals of Operations Research, 107(1), 15–32.

Agnetis, A., Hall, N. G., & Pacciarelli, D. (2006). Supply chain scheduling: Sequence coordination. Discrete Applied Mathematics, 154(15), 2044–2063.

Agnetis, A., Chen, B., Nicosia, G., & Pacifici, A. (2019). Price of fairness in two-agent single-machine scheduling problems. European Journal of Operational Research, 276(1), 79–87.

van den Akker, M., Hoogeveen, H., & Stoef, J. (2018). Combining two-stage stochastic programming and recoverable robustness to minimize the number of late jobs in the case of uncertain processing times. Journal of Scheduling, 21(6), 607–617.

Alfieri, A., Nicosia, G., Pacifici, A., & Pferschy, U. (2018a). Constrained job rearrangements on a single machine. AIRO Springer seriesIn P. Daniele & L. Scrimali (Eds.), New trends in emerging complex real life problems (Vol. 1, pp. 33–41). Berlin: Springer.

Alfieri, A., Nicosia, G., Pacifici, A., & Pferschy, U. (2018b). Single machine scheduling with bounded job rearrangements. In Proceedings of 16th Cologne-Twente workshop on graphs and combinatorial optimization (pp. 124–127).

Ballestín, F., Pérez, A., & Quintanilla, S. (2019). Scheduling and rescheduling elective patients in operating rooms to minimise the percentage of tardy patients. Journal of Scheduling, 22(1), 107–118.

Baptiste, P. (1999). Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times. Journal of Scheduling, 2(6), 245–252.

Blazewicz, J., Pesch, E., Sterna, M., & Werner, F. (2005). The two-machine flow-shop problem with weighted late work criterion and common due date. European Journal of Operational Research, 165(2), 408–415.

Daniels, R. L., & Kouvelis, P. (1995). Robust scheduling to hedge against processing time uncertainty in single-stage production. Management Science, 42(2), 363–737.

Detti, P., Nicosia, G., Pacifici, A., Manrique, Zabalo, & de Lara, G. (2019). Robust single machine scheduling with a flexible maintenance activity. Computers & Operations Research, 107, 19–31.

Hall, N. G., & Potts, C. N. (2010). Rescheduling for job unavailability. Operations Research, 58(3), 746–755.

Hall, N. G., Liu, Z., & Potts, C. N. (2007). Rescheduling for multiple new orders. INFORMS Journal on Computing, 19(4), 633–645.

Ivanov, D., & Sokolov, B. (2015). Coordination of the supply chain schedules with re-scheduling considerations. IFAC-PapersOnLine, 48(3), 1509–1514.

Leung, J. Y. T., Pinedo, M., & Wan, G. (2010). Competitive two-agent scheduling and its applications. Operations Research, 58(2), 458–469.

Li, X., Ventura, J. A., & Bunn, K. A. (2021). A joint order acceptance and scheduling problem with earliness and tardiness penalties considering overtime. Journal of Scheduling, 24, 49–68.

Liebchen C, Lübbecke M, Möhring R, Stiller S (2009) The Concept of recoverable robustness, linear programming recovery, and railway applications. In Robust and online large-scale optimization: Models and techniques for transportation systems (vol. 5868, pp. 1–27). Springer.

Nicosia, G., Pacifici, A., Pferschy, U., Polimeno, E., & Righini, G. (2019). Optimally rescheduling jobs under LIFO constraints. In Proceedings of the 17th Cologne-Twente workshop on graphs and combinatorial optimization (pp. 107–110).

Niu, S., Song, S., Ding, J. Y., Zhang, Y., & Chiong, R. (2019). Distributionally robust single machine scheduling with the total tardiness criterion. Computers & Operations Research, 101, 13–28.

Nouiri, M., Bekrar, A., Jemai, A., Ammari, A. C., & Niar, S. (2018). A new rescheduling heuristic for flexible job shop problem with machine disruption. Studies in Computational Intelligence, 762, 461–476.

Ouelhadj, D., & Petrovic, S. (2009). A survey of dynamic scheduling in manufacturing systems. Journal of Scheduling, 12(4), 417–431.

Perez-Gonzalez, P., & Framinan, J. M. (2014). A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: Multi-agent scheduling problems. European Journal of Operational Research, 235(1), 1–16.

Potts, C. N., & Van Wassenhove, L. N. (1988). Algorithms for scheduling a single machine to minimize the weighted number of late jobs. Management Science, 34(7), 843–858.

Vieira, G. E., Herrmann, J. W., & Lin, E. (2003). Rescheduling manufacturing systems: A framework of strategies, policies, and methods. Journal of Scheduling, 6(1), 39–62.

Wu, S. D., Storer, R. H., & Chang, P. C. (1993). One machine rescheduling heuristics with efficiency and stability as criteria. Computers & Operations Research, 20(1), 1–14.

Thông tin
Thông tin xuất bản

Journal of Scheduling

Thông tin tác giả