Two-machine flow shop with dynamic storage space
- PDF / 421,480 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 80 Downloads / 183 Views
Two-machine flow shop with dynamic storage space 1 Joanna Berlinska ´
· Alexander Kononov2,3 · Yakov Zinder4
Received: 31 March 2020 / Accepted: 8 September 2020 © The Author(s) 2020
Abstract The publications on two-machine flow shop scheduling problems with job dependent storage requirements, where a job seizes a portion of the storage space for the entire duration of its processing, were motivated by various applications ranging from supply chains of mineral resources to multimedia systems. In contrast to the previous publications that assumed that the availability of the storage space remains unchanged, this paper is concerned with a more general case when the availability is a function of time. It strengthens the previously published result concerning the existence of an optimal permutation schedule, shows that the variable storage space availability leads to the NP-hardness in the strong sense even for unit processing times, and presents a polynomial-time approximation scheme together with several heuristic algorithms. The heuristics are evaluated by means of computational experiments. Keywords Two-machine flow shop · Makespan · Dynamic storage · Computational complexity · Polynomial-time approximation scheme
1 Introduction This paper is concerned with the two-machine flow shop scheduling problem. This problem is widely used for modelling various real-world situations which can be viewed as a problem of scheduling a set of jobs on two machines, the first-stage
B
Joanna Berli´nska [email protected] Alexander Kononov [email protected] Yakov Zinder [email protected]
1
Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznan, Poland
2
Sobolev Institute of Mathematics, Novosibirsk, Russia
3
Novosibirsk State University, Novosibirsk, Russia
4
School of Mathematical and Physical Sciences, University of Technology Sydney, Sydney, Australia
123
J. Berlinska ´ et al.
machine and the second-stage machine [6]. According to the two-machine flow shop model, each job should be processed on the first-stage machine and, after the completion of this first operation, on the second-stage machine. The considered objective function is the total time needed for the completion of all jobs. In the literature on scheduling, the problems with this objective function are normally referred to as the makespan minimisation problems or simply makespan problems. A number of applications, ranging from multimedia systems [14] and star data gathering networks [1] to supply chains of mineral resources [7], motivated the recent interest in the two-machine flow shop with limited storage space, also referred to as the two-machine flow shop with job dependent buffer requirements. This direction of research focuses on the situations with two distinct characteristics: (1) each job requires some storage space and the storage requirements vary from job to job; and (2) each job seizes the required portion of the storage space (buffer) from the start of its first operation till the completion of it
Data Loading...
