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

Classical single-machine scheduling problems aim at finding an optimal sequence to process a set of jobs with given processing times possibly subject to additional constraints concerning, for instance, release dates, due dates, etc.

In several industrial settings, different unforeseen phenomena, such as data-obsolescence or disruptions, could deteriorate the performance (or optimality) of the planned ahead schedule. In this case, it is sometimes possible—or even necessary—to compute a new schedule by rearranging the previous job sequence. A similar situation frequently occurs, e.g., in lot production or in operating-rooms scheduling. In the first case, lots must typically go through several working stages: Between two of them, it may be beneficial to reorganize the sequence, owing to, for instance, different characteristics of the lots in the next stage. In the second case, a tentative schedule for a certain planning period is built in advance and, later on, the final schedule is output trying to minimize changes with respect to the original plan.

In this context, we are interested in the following problem: We are provided with an initial job sequence to feed a single processing resource; we need to rearrange the jobs such that the new sequence performs well in terms of some given criterion. Depending on the considered setting, we also need to deal with a given set of feasible reconfigurations (such restrictions may be imposed, e.g., by the physical handling system of the plant) which are, somehow, not too distant from the original sequence. A special version of this problem is also considered in Alfieri et al. (2018a, 2018b). The authors studied a rescheduling problem with the constraint that the jobs extracted from the given initial sequence can be re-inserted only in later positions, i.e., jobs can be postponed but not moved ahead of the schedule. This corresponds to a physical setting where jobs are transported on a conveyor that feeds a single processor and a robot or worker can pick them up and reinsert them later in the queue.

In this paper, we adopt a similar setting but with an additional set of restrictions. In particular, we consider the scenario in which the handling mechanism consists of a conveyor that feeds a single machine in a given sequence and a robot, placed along the line, that is able to alter this sequence. The robot may pick parts from the conveyor as they are moving, stacks them on a buffer of finite capacity from which it takes the parts and places them back on the conveyor, in their final positions (which is later in the original sequence due to the conveyor movement). Since the stack is managed according to a Last-In-First-Out (LIFO) policy, only the last part put into the stack can be extracted and re-inserted in the new sequence. This setting has been introduced in Nicosia et al. (2019) where the authors present some preliminary results on the corresponding rescheduling problem.

An area of research which is strictly related to the problem we address in this article, deals with sequence coordination in supply chain (SC). One of the main tasks in SC management is indeed coordination of several activities performed at different stages of the chain. An obvious overall goal consists in successfully meeting customers needs and achieving a good level of efficiency and performance. Usually, in a coordinated SC, two or more processes subject to their mutual coordination are considered. This involves fitting the schedules of different manufacturers together when some planned or unexpected schedule changes are experienced by one or more of them (Ivanov and Sokolov 2015). In this context, Agnetis et al. (2006) consider two consecutive stages of a supply chain where ideal job sequences (typically, different for the two stages) are given. The authors address a supply chain scheduling coordination problem consisting in finding a trade-off schedule that takes into account the ideal schedules of both stages. They propose a number of polynomial-time algorithms for different versions of the problem, namely from the point of view of the manufacturer, then from that of the supplier, and, finally, they consider the situation when both stages cooperate to obtain a satisfactory compromise schedule. A related coordination problem is addressed in Agnetis et al. (2001) where two departments in a manufacturing facility process the jobs in batches. In a first department, a setup is paid whenever a certain attribute changes from one batch to another, whereas in a second department, the setup is associated to a different attribute. The problem of finding a unique sequence of jobs in order to minimize the overall setup cost arises. The authors prove that the problem is NP-hard and propose an effective heuristic approach. The above coordination problems are also tightly connected to those addressed in multi-agent scheduling, a research field which received great attention more recently: Two or more agents have to agree on a fair, i.e., acceptable schedule of their distinct sets of jobs on a common processing resource [see, for instance, Leung et al. (2010), Perez-Gonzalez and Framinan (2014) and Agnetis et al. (2019)].

Another important and fruitful research stream, connected to the problem addressed here, concerns the so-called rescheduling (or dynamic scheduling). In many real-world scenarios, scheduling is an activity requiring frequent revisions due to unexpected changes such as, for instance, machine breakdown or unavailability, delay in the arrival of materials, job cancellation, due date changes, etc. With the terms rescheduling and dynamic scheduling, many authors indicate the problem of scheduling in the presence of real-time events; this includes the process of updating the current schedule to face previously unknown events such as the arrival of new jobs (Hall et al. 2007), disruptions (Nouiri et al. 2018), perturbation of the originally given or estimated data (Hall and Potts 2010), etc. A recent and effective application of these concepts in the health care sector can be found in Ballestín et al. (2019). Two different reviews of the state-of-the-art of currently developing research on dynamic scheduling are given in Ouelhadj and Petrovic (2009) and Vieira et al. (2003).

From the pioneering works by Daniels and Kouvelis (1995) and Wu et al. (1993) up to the most recent papers (see, e.g., Detti et al. 2019; Niu et al. 2019), robustness is a widely adopted concept in scheduling and it is an alternative (pro-active) approach that tries to design a schedule which a priori guarantees a certain level of efficiency, given a set of possible scenarios. This way stability is preserved while performance is kept above a fixed level.

Indeed, our problem can be viewed in the framework of the so-called recoverable robustness, see Liebchen et al. (2009). A recoverable robust solution is not necessarily feasible in all scenarios of a robust optimization problem, but it can be made feasible by applying a (simple, quick) recovery algorithm to it. This concept has been investigated in several application contexts (mostly in transportation problems) and there is a limited literature also in scheduling. For instance, in van den Akker et al. (2018) an initial solution of a scheduling problem is given and in each scenario some recovery actions are performed to make the solution acceptable again.

The algorithms presented in this work can be regarded as recovery algorithms to achieve certain objective benchmarks (rather than feasibility) in different problem settings which are illustrated below.

In the special rescheduling problem addressed in this paper, we consider several objective functions, namely total weighted completion time, maximum lateness, number of late jobs and weighted number of late jobs. We devise strictly polynomial-time optimization algorithms based on dynamic programming recursions for the first three objectives. In contrast, we prove that the problem is NP-hard when minimizing the weighted number of late jobs, but still permits a pseudo-polynomial dynamic programming algorithm in that case. The remainder of this work is organized as follows: After a rigorous statement of the problem in Sects. 2,  3, 4 and 5 are devoted to the first three objective functions and describe the corresponding efficient solution algorithms. For the problem with the weighted number of late jobs objective, in Section 6, we prove its complexity and propose a pseudo-polynomial algorithm. Section 7 illustrates by a short experimental study the behavior of the rescheduling process depending on the stack size. Finally, concluding remarks are given in Sect. 8.

In this section, we give a formal statement of the problem under consideration and introduce the notation used throughout the paper. Hereafter, we use the term “job” to refer to both, a physical piece of material which is processed by some machine or resource and the process itself (characterized by a certain duration and possible additional data).

Let us consider a deterministic single-machine environment where we are given a set J of n jobs that have to be scheduled according to a regular, i.e., non-decreasing, objective function \(f(\sigma )\) of the job completion times \(C_j(\sigma )\), \(j = 1,\ldots ,n\). For such a schedule \(\sigma = \langle \sigma _1, \sigma _2, \dots , \sigma _n \rangle \) with \(\sigma _k\in J\), \(k=1,\dots , n\), if \(i \le j\), we refer to the ordered set of jobs \(\langle \sigma _i,\sigma _{i+1},\ldots ,\sigma _j\rangle \) as the subsequence \(\sigma (i,j)\). Moreover, for each job \(j \in J\) we know its processing time \(p_j\) and, possibly, a due date \(d_j\) and a weight \(w_j\). As usual for scheduling problems, we will assume that all these values are nonnegative integers. However, this property will be required only for the dynamic programming algorithm in Sect. 6. Additionally, we are given an initial sequence \(\sigma _0\) in which the n jobs of set J are numbered from 1 to n. So, \(\sigma _0=\langle 1,2, \ldots , n \rangle \) and we say that job j is placed in the j-th position to indicate that it is the j-th job of the sequence \(\sigma _0\). Clearly, if \(i,j \in J\) and \(i\le j\), we have \(\sigma _0(i,j) = \langle i,i+1,\ldots ,j \rangle \).

In the problem addressed here, we look for a new job sequence \(\sigma \) such that Any move in this scheduling environment is performed by a physical device (e.g., a robot arm) that operates on a sequence of parts, each associated to one job, arranged in an ordered sequence along a line (e.g., on a moving conveyor). The initial sequence on this line corresponds to \(\sigma _0\). The considered device (i) picks up a job j; (ii) places j in the stack with bounded capacity S; (iii) possibly picks up other jobs and places them in the stack; (iv) picks the jobs from the stack, according to a LIFO policy, and places them back (on the conveyor) at a suitable position later in the sequence. We assume that there is always enough space between jobs to place even the whole content of the stack between any two jobs on the line.

In this setting, moved jobs can only be postponed, as in fact the robot arm picks the jobs from the line while the conveyor feeding the processor moves ahead. Hence, reinsertion can only happen in a later position of the sequence.

Definition 1 A move \(i\rightarrow j\), \(i<j\), consists of deleting job i from a given sequence and reinserting it immediately after all jobs of the subsequence \(\sigma _0(i+1,j)\).

Figure 1 illustrates the process for three consecutive moves on a sequence \(\sigma _0\) with \(n=9\) jobs. The picture emphasizes the characteristics of two types of feasible moves for the above mentioned physical device. A move \(1\rightarrow 3\) in which job 1 is placed immediately after job 3 is performed first. Then, moves \(5\rightarrow 9\) and \(7\rightarrow 9\) are done: Job 5 is loaded into the stack directly before 7, which is then extracted from the stack and placed just after job 9. After that, 5 is placed back on the line, right after 9 and 7. It is clear that the latter operations require that the stack capacity S is at least 2.

Observe that, if we start from \(\sigma _0\), due to the stack LIFO policy, Definition 1 is consistent even after a number of moves has been performed.

Following the above considerations, we are now characterizing the compatibility of two moves.

Definition 2 Two moves \(i_1\rightarrow j_1\) and \(i_2\rightarrow j_2\) with \(i_1<i_2\) are feasible if: Note that, as a consequence of Definition 1, it is easy to see thatWe next define the level of a move:

Definition 3 A move that does not contain nested moves is said to be at level 1. Recursively, a move m is at level \(\ell > 1\) if \(\ell \) is the smallest value such that m contains feasible nested moves at level up to \(\ell -1\).

Clearly, a move at level \(\ell \) is feasible only if \(\ell \le S\). In the example shown in Fig. 1, \(1 \rightarrow 3\) and \(5 \rightarrow 9\) are sequential moves while \(7 \rightarrow 9\) is nested in \(5 \rightarrow 9\). In particular, \(5 \rightarrow 9\) is at level 2.

In the remainder of this paper, we adopt the following definition for a move.

Definition 4 A move \(i\rightarrow j\) at level \(\ell \) is denoted as \((i,j,\ell )\). For notational convenience, we also define \((i, i, \ell )\) for every level \(\ell \), meaning that job i is not moved at all.

Note that in our setting the stack capacity constraint imposes the index \(\ell \) to be an integer within the range 1 to S, i.e., there must not be more than S moves nested inside each other.

Definition 5 The set of feasible schedules \({\mathcal {F}}_S\) for the rescheduling problem where the stack capacity is limited by S, is comprised of all the schedules resulting from a set of feasible moves at levels up to a maximum of S starting from \(\sigma _0\).

In this paper, we consider the minimization of three classical objective functions in scheduling theory to evaluate the sequence obtained from \(\sigma _0\) through the LIFO-constrained moves: total weighted completion time, maximum lateness (with extension to any regular function) and number of late jobs. For the latter, we consider both, the weighted and unweighted case.

For any feasible schedule \(\sigma \) of the jobs of J and any job \(j \in J\), we define the following quantities: \(C_j\left( \sigma \right) \) is the completion time of j in \(\sigma \), \(L_j\left( \sigma \right) = C_j\left( \sigma \right) - d_j\) is the lateness of job j in \(\sigma \) andindicates if job j is late. Note that the completion time of job j in the initial sequence \(\sigma _0\) is given by \(C_j(\sigma _0) = \sum _{k=1}^j p_k\) and its lateness by \(L_j(\sigma _0)\). We indicate with \(P(i,j) = \sum _{k = i}^{j} p_k\) the total processing time of the subsequence \(\sigma _0(i,j)\) and with \(W(i,j) = \sum _{k=i}^j w_k\) its total weight. Moreover, for a given subsequence \(\sigma (i,j)\), the maximum lateness within the subsequence isFurthermore, if \(\phi _j: {\mathbb {R}}_{\ge 0} \rightarrow {\mathbb {R}}\), \(j \in J\), are given regular functions, we denote the maximum of regular function objective asIn accordance with the standard Graham’s three field notation, we indicate the problems addressed in this paper as follows: \(1|{\text {resch-LIFO}}|\sum w_j C_j\), \(1|{\text {resch-LIFO}}|L_{\max }\), \(1|{\text {resch-LIFO}}|\Phi _{\max }\), \(1|{\text {resch-LIFO}}|\sum U_j\) and \(1|{\text {resch-LIFO}}|\sum w_j U_j\) where the last field refers to the particular objective we want to minimize in rearranging the given initial schedule \(\sigma _0\) through the above described mechanism.

In this paper, we also consider the following special generalization of the above problems. Let \(\Omega \subseteq J\) be a given subset of movable jobs and consider as feasible solutions only the schedules obtained from \(\sigma _0\) by a set of feasible moves (at levels up to a maximum of S), where only moves \(i \rightarrow j\) with \(i \in \Omega \) are involved. Jobs from \(J\setminus \Omega \) cannot be moved, whereas jobs from \(\Omega \) may be moved but it is not mandatory to move them. In the remainder of the paper, we will refer to this variant as \(\Omega \)-constrained problem. Observe that our original rescheduling problems are special cases of these \(\Omega \)-constrained problems in which \(\Omega = J\).

We start our study by considering the minimization of the weighted sum of job completion times, for which we present a polynomial time dynamic program.

First, we can observe that for any partition of a schedule \(\sigma = \langle \sigma _1, \sigma _2, \ldots ,\sigma _n \rangle \) in Q adjacent subsequences \(\sigma (u_q,v_q) = \langle \sigma _{u_q},\ldots ,\sigma _{v_q} \rangle \) with \(u_q \le v_q\) such that \(u_1=1\), \(v_Q=n\) and \(u_q = v_{q-1} + 1\) for all \(q=2,\ldots ,Q\), the objective function can be expressed as follows:where the term \(f^{(1)}\left( \sigma (u_q,v_q)\right) \) denotes the total weighted completion time for the subsequence \(\sigma (u_q,v_q)\), which in turn is the sum of the weighted completion times of the jobs in the subsequence. Denoting by \(J_q\) the set of jobs of subsequence \(\sigma (u_q,v_q)\), clearly we have:Consider the set \({\mathcal {M}}\) of all feasible moves \((i,j,\ell )\) that allows to reach \(\sigma \) starting from \(\sigma _0\). Let \(\mathcal {{\widetilde{M}}}\subseteq {\mathcal {M}}\) indicate the set of moves \((i,j,\ell )\) which are not nested in any other move \((h,k,\ell ')\in {\mathcal {M}}\) at a higher level \(\ell '>\ell \). By definition, the moves \(\mathcal {{\widetilde{M}}}\) are sequential moves. In \(\mathcal {{\widetilde{M}}}\), we also include identity moves (i, i, 1) which correspond to not moving job i. (Clearly, parts of \(\sigma \) which are unchanged with respect to \(\sigma _0\), i.e., if the subsequence \(\sigma (i,j)=\sigma _0(i,j)\), can be represented by a set of consecutive identity moves (k, k, 1) with \(k=i, \dots , j\).) Let us denote \(\mathcal {{\widetilde{M}}}\) as follows:with \(1= u_1 \le v_1\), \(v_r = n\), \(v_{q-1} + 1 = u_{q} \le v_q\), \(q=2,\ldots , r\). (Note that r in (3) plays a different role than Q in (2).) Because of the additivity principle (1), the cost \(f^{(1)}(\sigma )\) of schedule \(\sigma \) can be computed by adding—to the cost of \(\sigma _0\)—the contributions of the r feasible moves of \({\widetilde{{\mathcal {M}}}}\). Note that in (3) each move \((u_q,v_q,\ell _q)\) may contain nested moves, so that its contribution depends on these nested moves as well. For instance, the sequential moves of \({\widetilde{{\mathcal {M}}}}\) in the example illustrated by Fig. 1 are (1, 3, 1), (4, 4, 1) and (5, 9, 2). Move (5, 9, 2) contains the nested move (7, 9, 1), and therefore, its contribution must also account for the one of (7, 9, 1).

Hereafter, we present a dynamic programming algorithm for determining the optimal set of moves yielding a minimum cost schedule \(\sigma ^*\), starting from \(\sigma _0\). The correctness of this algorithm straightforwardly follows from the following observation which corresponds to a standard optimality principle: In any optimal schedule \(\sigma ^*\), there exists a partition as in (3), such that each subsequence in the partition is optimal for the subproblem containing only the jobs of that subsequence. The basic step of the dynamic program consists of computing the cost of a move \((i,j,\ell )\), at level \(\ell \) based on the knowledge of optimal costs for any subsequence of \(\sigma (i,j)\) in which the stack capacity is \(\ell - 1\).

Definition 6 The cost \(c(i,j,\ell )\) is defined as the minimum total weighted completion time variation when a move \((i,j,\ell ')\) at some level \(\ell ' \le \ell \) is performed. The cost \(\mu ^*(i,j,\ell )\) is the minimum cost variation of subsequence \(\sigma _0(i,j)\), when the stack capacity is equal to \(\ell \).

Observe that \(c(i,j,\ell )\) includes the optimal cost variation produced by all possible nested moves at lower levels, and hence, it takes into account information of all \(c(h,k,\ell -1)\) for \(i<h\le k\le j\) which in turn are summed up into \(\mu ^*(i+1,j,\ell -1)\). While \(\mu ^*(i,j,\ell )\) gives the optimal cost variation for the subproblem implied by i and j, \(c(i,j,\ell )\) considers the particular solution where the move \(i\rightarrow j\) must be performed.

Observation 7 The completion time of each job preceding i and following j in the initial sequence \(\sigma _0\) is not affected by the move \((i,j,\ell )\).

Based on the initial schedule \(\sigma _0\), the cost variation m(i, j) due to moving job i after job j is expressed asThe first term in (4) indicates the increase of the weighted completion time of job i, while the second term indicates the total decrease of the weighted completion times of the jobs in \(\sigma _0(i+1,j)\). In addition, because of the definition of the cost of a move (4), it is easy to verify the following:

Observation 8 The effect of a move \((i,j,\ell )\) at any level \(\ell >1\) does not depend on the order of the jobs in the subsequence \(\sigma _0\left( i+1,j\right) \).

As a consequence, because of the LIFO constraint, the cost variation due to a single move \((i,j,\ell )\) is always equal to m(i, j), for all possible levels \(\ell \).

As far as sequential moves are concerned, we recall that, owing to Eq. (1), the effect of two sequential moves \((i_1,j_1,\ell _1)\) and \((i_2,j_2,\ell _2)\), \(j_1 < i_2\), on the objective \(f^{(1)}\) equals the sum of the effects of each move.

Moves at level \(\ell = 1\) cannot contain any nested moves, so the cost c(i, j, 1) of a move is equal to m(i, j). Obviously, when a job i is not moved, the associated cost is null and \(c(i,i,1)=0\). Hence, we may give a recursive expression of the optimal cost variation for the subsequence \(\sigma _0(i,j)\) as follows:Even when dealing with nested moves, i.e., for \(\ell >1\), the cost variation of a set of moves is additive: Following the same line of arguments yielding to Observation 8 and Eq. (4), the overall effect on \(f^{(1)}\) of two (or more) nested moves is equal to the sum of the effects of each move.

In order to compute the cost \(c(i,j,\ell )\) for a move \((i,j,\ell ')\) with \(\ell ' \le \ell \), one clearly has to take into account the possibility of optimally rearranging the subsequence \(\sigma _0(i+1,j)\) with moves at levels lower than \(\ell '\). Thus, after computing all optimal cost variations \(\mu ^*(i,j,\ell -1)\) obtainable from a set of moves up to level \(\ell -1\) for the subsequence \(\sigma _0(i,j)\), it is possible to determine the (optimal) cost \(c(i,j,\ell )\). This in turn allows to compute the optimal cost variation \(\mu ^*(i,j,\ell )\) for the subsequence \(\sigma _0(i,j)\) at level \(\ell \). Formally, the following recursion holds:In Eq. (6), \(\mu ^*(i,j,\ell )\) is computed in a similar way as in (5):Finally, the optimal solution value is found by computing \(\mu ^*(1,n,S)\) such that the objective function value of the optimal schedule equalsAs for the computational complexity of the above dynamic program, we observe that the computation of all m(i, j), i.e., the costs at level \(\ell =1\), requires \(O(n^2)\) time. For each level \(\ell = 1,\ldots ,S\) and for each ordered pair of jobs (i, j), the algorithm must compute the cost \(c(i,j,\ell )\) of the corresponding move and the optimal subsequence cost \(\mu ^*(i,j,\ell )\). Computing all c values requires \(O(n^2)\) time at each level, since each value is computed in O(1), while the computation of \(\mu ^*(i,j,\ell )\) in Eq. (7) has a cost of \(O(n^3)\) time for each level \(\ell \). Hence, the overall complexity of the algorithm is \(O(n^3 S)\) which is upper bounded by \(O(n^4)\).

The results above can be summarized as follows.

In this section, we first focus on the minimization of the maximum lateness of the jobs and present a dynamic programming solution algorithm related to the one presented in the previous Sect. 3. We then discuss how the same algorithm can be used to solve the more general problem \(1|{\text {resch-LIFO}}|\Phi _{\max }\).

This section provides a dynamic programming algorithm to minimize the number of late jobs, \(f^{(3)}(\sigma ) = \sum _{j \in J} U_j(\sigma )\), where the quantity \(U_j(\sigma )\) assumes value 1 if and only if job j is late in schedule \(\sigma \), i.e., if its lateness \(L_j(\sigma )\) is strictly positive.

Given a subsequence of a schedule, the number of late jobs in this subsequence depends not only on the processing times and due dates of the jobs in this subsequence, but generally also on its starting time. As a consequence, an (optimal) rearrangement of a subsequence that minimizes the number of late jobs depends on its starting time. This is illustrated in the following example: consider the sequence \(\sigma = \langle 1,2,3 \rangle \) with \(p_1 = 7\), \(p_2 = p_3 = 10\), \(d_1 = d_2 = 25\) and \(d_3 = 15\). It is easy to see that, in order to minimize the number of late jobs in the subsequence \(\sigma (2, 3)\), the ordering \(\langle 3,2 \rangle \) should be preferred if the sequence starts at \(t=0\) (i.e., move \(1 \rightarrow 3\) is performed), whereas for \(t = 7\) (i.e., job 1 is not moved) the arrangement \(\langle 2,3 \rangle \) is better. However, the following result indicates that the relative order of the lateness values is independent from the starting time of a subsequence.

Observation 13 Let \(\sigma _q(i,j)\) be a feasible arrangement of the subsequence \(\sigma (i,j)\) that minimizes the q-th largest lateness value, \(q=1,\ldots ,j-i+1\). Then, \(\sigma _q(i,j)\) does not depend on the starting time of \(\sigma _q(i,j)\).

Note that in general the arrangements minimizing the q-th largest lateness are different for different values of q. However, when a subsequence is moved earlier (or delayed), all lateness values decrease (or increase) by the same amount, and hence, their order remains unchanged. Observation 13 holds for any possible definition of “feasible arrangement”; in particular, in this paper we clearly refer to the set of sequences resulting from a set of feasible moves at levels up to a given maximum.

In the reminder of this section, we refer to \(\ell \)-rearrangement to indicate a feasible rearrangement of a subsequence that can be obtained by moves up to level \(\ell \).

Here, we deal with a generalization of the problem introduced in the previous Sect. 5, and consider different job priorities. We therefore introduce a cost, associated to each job, which is paid if that job is late. This type of objective is studied in a number of papers (see, e.g., Baptiste 1999; Blazewicz et al. 2005). We first prove that the resulting problem, namely \(1|{\text {resch-LIFO}}|\sum w_j U_j\), is NP-hard and then present a pseudo-polynomial exact solution algorithm based on dynamic programming.

In this section, we illustrate the effect of rescheduling and in particular the influence of the stack size for the three polynomial time algorithms presented in Sects. 3 to 5. We do not report running times. We only observe that the dynamic programming algorithms show quite small deviations in running times for instances of the same size.

As a test bed, we follow the data generation scheme by Potts and Van Wassenhove (1988). We choose processing times and weights independent and identically, uniformly distributed with \(p_j \sim U(1, 100)\) and \(w_j \sim U(1, 100)\). For two parameters \(d^\ell \) and \(d^u\) we choose \(d_j \sim U(P(1,n)\,d^\ell ,\, P(1,n)\,d^u)\). We consider four choices for \(d^\ell \), namely \(d^\ell \in \{0.2, 0.4, 0.6, 0.8\}\), and all possibilities for \(d^u \in \{0.2, 0.4, 0.6, 0.8, 1.0\}\) with \(d^\ell \le d^u\), which yields 14 pairs of parameter values. For the number of jobs, we take \(n=50\) and \(n=100\). For each of the 28 resulting classes of instances, 20 instances were randomly generated, i.e., 560 instances in total.

The goal of our analysis is twofold: We want to analyze the potential improvement of the objective function obtained through rescheduling and we want to illustrate the utilization of the stack. Naturally, both aspects strongly depend on the stack size. Therefore, all our evaluations are performed for increasing stack sizes, starting from \(S=1\) up to \(S=25\). Note that for practical applications in a production setting, the LIFO stack can be expected to be of moderate size with \(S\le 10\), but for the empirical analysis we consider also larger values of S. It is also clear that S does not depend on the number of jobs.

The results of our tests are given in Figs. 3, 4 and 5. All values are taken as averages over the 280 instances for \(n=50\) and \(n=100\), respectively.

The two graphs in the upper row of each figure describe the effect of rescheduling on the solution. In Figs. 3a, 4a and 5a, we give the gap between the solution obtained from rescheduling under LIFO constraints with a certain stack size (given on the x-axis) and the optimal schedule (obtained by completely reordering the given jobs). For \(1|{\text {resch-LIFO}}|\sum w_j C_j\), the gap in Fig. 3a is the difference relative to the total weighted completion time of an optimal schedule expressed in percent. For \(1|{\text {resch-LIFO}}|L_{\max }\), it is not obvious how to scale the difference to the optimal schedule since the latter could have a positive, zero or negative maximum lateness. Thus, we take the difference between lateness after rescheduling and lateness of an optimal schedule and divide it by \(C_{\max } = P(1,n)\), see Fig. 4a. Finally, for \(1|{\text {resch-LIFO}}|\sum U_j\) the difference of the number of late jobs is given as an absolute value in Fig. 5a (note that the optimal value might be zero). It can be seen that there is a certain limit on the effect reachable by rescheduling, e.g., for total weighted completion time the gap hardly gets below 20%. This is possibly due to the LIFO constraint.

In Figs. 3b, 4b and 5b, we give the number of moves, i.e., the total number of jobs inserted into the stack during the rescheduling process. As can be expected, a larger stack size permits much more improvement of the solution and reschedules a larger proportion of the jobs. But from a certain stack size, the objective improves only marginally and thus also the number of moves ceases to grow.

The two graphs in the lower row of each figure describe the stack utilization. In Figs. 3c, 4c and 5c, the maximum stack utilization is given, i.e., the largest number of jobs contained in the stack at any time during the rescheduling process. It turns out that for the total weighted completion time the stack size is almost always fully exploited at some point of the execution. This is not the case when minimizing maximum lateness, especially for the smaller instances with \(n=50\), where a close to optimal solution is reached with a moderate stack size, but further improvements are reachable only for a few instances as the stack size increases. If the number of late jobs is minimized, the stack size can be mostly fully exploited for the larger instances with \(n=100\), while for \(n=50\) an almost optimal solution is reachable even with \(S\approx 15\) (as can be seen from Fig. 5a), and thus, the stack is not fully utilized (see Fig. 5c).

Finally, Figs. 3d, 4d and 5d show the average stack utilization. This means that we track the number of jobs contained in the stack in each of the \(n-1\) steps of the rescheduling process and take their average. Clearly, this includes a certain phasing-in and phasing-out effect since the empty stack only starts accepting jobs at the beginning and has to be empty again until the end of the sequence. The concave shape of the corresponding figures is due to this effect which is naturally much stronger for \(n=50\) than for \(n=100\). It turns out that for maximum lateness the average stack utilization is considerably smaller than for total weighted completion time (compare Figs. 3d and 4d) with number of late jobs as a close follower. We believe that this is due to the fact that for total weighted completion time the optimal solution is unique (for distinct input values) while for the other two objectives there usually exist various different sequences with the same solution value. Once an optimal or very good solution value is reached, further rearrangements of the sequence are not beneficial any more.

In this paper, motivated by questions arising in manufacturing applications, we study the problem of rearranging a given sequence of jobs on a single machine in order to minimize one of four different objectives. We rely on the standard scheduling parameters of a job, namely processing time, weight (importance) and due date. From a practical point of view, also operating costs arising from the rearrangement steps, in particular energy consumption, could be taken explicitly into account.

The new sequence can be obtained respecting certain technological constraints: In particular, our jobs are associated to physical parts, sequenced on a conveyor that feeds a processing resource, which can be picked up by a robot. A job taken from the conveyor by the robot is first put into a buffer and then placed again on the conveyor in a later position of the original sequence. The buffer is managed as a stack with limited capacity so the last job entering the buffer is the first taken by the robot to be put down again on the conveyor. Due to this LIFO mechanism, only a certain set of sequences can be reached starting from the initial one and this set constitutes all the feasible solutions of our problems.

Our contribution is focused on settling the computational complexity and providing exact solution algorithms. In particular, we are able to provide strongly polynomial (dynamic programming) solution algorithms for the minimization of (i) total weighted completion time of the jobs, (ii) maximum of regular functions of the completion times, in particular maximum lateness, of the jobs, and (iii) number of late jobs. We also prove that (iv) if we want to minimize the weighted number of late jobs, then the problem becomes (weakly) NP-hard. For the latter problem, we present a pseudo-polynomial solution algorithm (again based on a dynamic program).

Future research should consider an empirical study concerning both the characterization of optimal solutions, that may be obtained starting from different input sequences, and the performance of exact solution algorithms in terms of numerical efficiency, with possible comparisons with alternative enumeration schemes.

In more general terms, it would clearly be interesting to consider other regimes for buffer management. From a practical point of view, the most relevant setting would be a queue environment implied by a FIFO mechanism. Of course, also a random access buffer where any job can be taken from the buffer, may be well justified, although technically more complicated. These two aspects will be subject of future research. Moreover, it would also be interesting to consider alternative performance figures. We dealt with the four most common, standard objectives functions, but in the future also other choices might be relevant, in particular in the context of a real-world application (Li et al. 2021).