Solutions to Real-World Instances of PSPACE-Complete Stacking Problems

This project delves into the PSPACE-complete stacking problem, motivated by its application in steel plant logistics, particularly the storage and transportation of steel slabs. The project formulates the problem broadly to encompass various manufacturing scenarios, considering constraints such as time windows, precedence relations, and stack heights. The core of the problem involves optimizing the stacking of items from inputs to buffer stacks and then to target stacks, minimizing the number of moves required. The analysis includes the development of a conflict graph to model stacking restrictions and a discussion of the problem's complexity, concluding that the stacking problem is in PSPACE. The project references relevant research and solutions, showcasing the applicability of theoretical concepts to real-world industrial challenges, and explores the use of genetic algorithms to solve the stacking problem.

Running Head: SOLUTIONS TO REAL-WORLD INSTANCES OF PSPACE-COMPLETE STACKING 1
SOLUTIONS TO REAL-WORLD INSTANCES OF PSPACE-COMPLETE STACKING
Name
Institution

SOLUTIONS TO REAL-WORLD INSTANCES OF PSPACE-COMPLETE STACKING 2
Introduction
The investigation done on this paper is for a dynamic problem that has various
application processes on the intermediate stacking of bulky items in society. The motivation of
our work is because of co-operation with PSI-BT which is a software company that deals with
the development of software for the planning of logistics of production in steel plants (Asai,
2018). The main task in this kind of a plant is the transporting and the storing steel plants for a
period of time something that has become the model of a universal dilemma for stacking that is
under consideration here. Similarly, it happens in the rest of settings, for instance, the rail car
shunting or containers’ stowage. We, therefore, maintain the formulation of our problem broad
properly to make a provision for a brief, hypothetically attractive problem category, and still
more precise to be applied to various manufacturing scenarios. In reality, various constraints
need to be respected (Wolf, 2017). These are the likes of time windows, precedence relations,
and stack heights. However, there exists no other formulation of a problem like this that has been
given before leave alone their solution of proven quality.
The motivation behind this problem is because, during the production of steel, bar casting
is done 24/7. The bars are 12 meters long and 30 tonnes in mass (Bohlin, Hansmann, &
Zimmermann, 2018). They are then rolled in according to this batch procedure. Every slab is put
under a buyer’s order prior to casting and thus becomes personal. Crane then brings the slabs to
the storage spaces and then arranged up in stacks for some days. In case the slabs are required
some days later, they might be taken from the hot buffer, then, for the time being, be put in a
bigger cold-buffer. We find that stacks number in both cases are limited in height. The main idea
should be that in hot-buffer, the slabs storage ought to ensure easier retrieval when required in
accordance with rolling process batch no (Fechter, Beham, Wagner, & Affenzeller, 2015). This

SOLUTIONS TO REAL-WORLD INSTANCES OF PSPACE-COMPLETE STACKING 3
is the reason there are conflicts because of the little space, the casting sequence as well as the
complicating reality and that the existing slab caster needs to be taken to another place in tight
time windows. Cold-buffers time factor is not important, instead, the system inbuilt non-
conformity series of output or input is greatly extra noticeable. Thus buffers represent key
drawback hence a high production is needed.
A description was made earlier concerning what the stacking problem is. Some few
practical events were omitted that have some relevant details; we are going to mention these
wherever fitting. Let [n]:= {1,…, n} objects coming in. Then there is a set of I: = [n] of objects
coming in that come over time on inputs that are parallel to m. We mark the input where item i €
I is provided by si € [m]. every object i €I is linked to time, a time window [ri, di] ḉ R +; ri which
is the time of letting go whereas di the remaining time of item i. an object ought to be taken
starting from input inside its time windows period. This can be done by moving directly to one of
the target stacks or to k-buffers as defined below. The assumption made is that at whichever
time, at least at every input an object is in existence.
Stacks of buffer
Allow s to be equal to ={S1,…,Sk} such that s: ={S1,…,Sk} representing a buffer stack
set. h(S) items can be held in Stack S €. A representation of a stack S is made by an ordered
sequence hS(1),.., S(h(S))i of items (from top to bottom); define S(x):=0 if no item is found at
position x. items allocation to stack C:= (S1,…, SK) together with positions of their
representatives is known as configuration. Co’s first configuration shouldn’t be empty. J e notes
objects that are assigned to buffer stacks in C0. The whole item set hence is V:=I ᴗ J.

SOLUTIONS TO REAL-WORLD INSTANCES OF PSPACE-COMPLETE STACKING 4
Constraints of stacking
There exist some constraints of stacking for the instant placing of items may not be done
on top of each other. In this case, it is written as i → S j iff i lies straight above j in stack S, this
means that i →S j iff S(x) = I, S(x -1) = j. similarly, we also write i S j iff I lies, it isn’t
essentially direct but above j in S. Similar notations are used for the stacks defined below. The
stacking restrictions are modeled by a graph of conflict. Allow G :=(V,A) be a direct graph with
the highest point made to be V, also curve set to be A. object i € V can’t be positioned straight
above object j iff (i, j) € A. an arrangement of C is called to be equal to (S1,…,Sk) possible if
every stack of buffer S € S has at least h(S) objects and for all that i, j € V in that i →S j, we have
(i, j) €/A. we believe that the original design C0 is possible (Ederer, Hartisch, Lorenz, Opfer, &
Wolf, 2017).
Stacks target
Considering set T := {T1, T2,…,Tℓ} of piles. Every pile T = hT(1), T(2),…i € T makes a
specification of an order where items representative collection happens. Only w target piles can
be accessed simultaneously. When the collection of all the target stacks has been done, we may
dispose of this target stack or move away. The times of transportation are recognized but are
crucial for practicability alone because they are little in comparison to lift up and times of drop-
off times (Marolt, Rupnik, & Lerher, 2019). Therefore, our plan is building the stacks that are
targeted starting from the first pattern using the least number of moves.

SOLUTIONS TO REAL-WORLD INSTANCES OF PSPACE-COMPLETE STACKING 5
Conclusion
In conclusion, the problem of stacking is in PSPACE (Kohlhase, 2019). After exploiting
Savitch’s theorem which says that “the equality amid the complexity classes PSPACE AND
NPSPACE in the representation of any arrangement of the problem of stacking in the polynomial
gap can be achieved”. Additionally, a computation in polynomial time of all possible moves
from a given configuration can be done. Thus a nondeterministic search with the use of
polynomial space can be performed. In each step, one of the possible moves can be chosen non-
deterministically keep track of the current state only. According to Savitch, his theory we learn
that a transformation of any algorithm into deterministic one is possible (Olsen, & Gross, 2015).

SOLUTIONS TO REAL-WORLD INSTANCES OF PSPACE-COMPLETE STACKING 6
References
Asai, M. (2018). Photo-Realistic Blocksworld Dataset. arXiv preprint arXiv:1812.01818.
Bohlin, M., Hansmann, R., & Zimmermann, U. T. (2018). Optimization of Railway Freight
Shunting. In Handbook of Optimization in the Railway Industry (pp. 181-212). Springer,
Cham.
Ederer, T., Hartisch, M., Lorenz, U., Opfer, T., & Wolf, J. (2017, July). Yasol: An open source
solver for quantified mixed integer programs. In Advances in Computer Games (pp. 224-
233). Springer, Cham.
Fechter, J., Beham, A., Wagner, S., & Affenzeller, M. (2015, February). Modeling a Lot-Aware
Slab Stack Shuffling Problem. In International Conference on Computer Aided Systems
Theory (pp. 334-341). Springer, Cham.
Kohlhase, M. (2019). Artificial Intelligence (Künstliche Intelligenz 1) Summer Semester
2018/19–Lecture Notes–Part III: Knowledge and Inference.
Marolt, J., Rupnik, B., & Lerher, T. (2019, March). Stack Shuffling Optimization of Steel Bars
by Using Genetic Algorithms. In Interdisciplinary Conference on Production, Logistics
and Traffic (pp. 20-31). Springer, Cham.
Olsen, M., & Gross, A. (2015, September). Probabilistic analysis of online stacking algorithms.
In International Conference on Computational Logistics (pp. 358-369). Springer, Cham.
Wolf, J. (2017, December). Yasol: An Open Source Solver for Quantified Mixed Integer
Programs. In Advances in Computer Games: 15th International Conferences, ACG 2017,

SOLUTIONS TO REAL-WORLD INSTANCES OF PSPACE-COMPLETE STACKING 7
Leiden, The Netherlands, July 3–5, 2017, Revised Selected Papers(Vol. 10664, p. 224).
Springer.