Expanding Flow Shop Tasks Based on Recursive Functions

Boris Kupriyanov Alexander Lazarev Aleksandr Roschin and Frank Werner \corrauth · 2026

Read Expanding Flow Shop Tasks Based on Recursive Functions by Boris Kupriyanov Alexander Lazarev Aleksandr Roschin and Frank Werner \corrauth (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-12077.txt.

Introduction

Kupriyanov, Lazarev, Roschin, and Werner widen flow shop scheduling through recursive functions. One recursive frame can hold six extensions of the classic problem at once. Three function types do the work: one tied to machines, one adjusting processing times, and one guarding feasibility. The authors lay out how these functions stack and how objectives take recursive form. General rules and properties for such functions follow. Simple cases then show how to phrase new problems ready for branch and bound.

Catalog record

CREATORBoris Kupriyanov Alexander Lazarev Aleksandr Roschin and Frank Werner \corrauth
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65062
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.12077

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Expanding Flow Shop Tasks Based on Recursive Functions Boris Kupriyanov Alexander Lazarev Aleksandr Roschin and Frank Werner \corrauth Abstract The paper discusses several extensions of the recursive representation of the flow shop scheduling problem. It is shown that recursive functions make it possible to describe multiple extensions in a single problem. The paper considers altogether six extensions. The examples consider three types of recursive functions: functions associated with the machine, functions that adjust the procession time based on constraints, and functions that control the feasibility of the schedule. The structure of the superpositions of these functions is presented, and also descriptions of several objective functions by recursive functions are presented. Then the general requirements for a recursive function are formulated and its properties are described. Finally, a demonstration of the formulation of new problems is provided using examples of simple flow shop extensions and branch and bound optimization. \corraddr [email protected]; Tel: +49-391-6752025; Fax: +49 391 6741171. keywords flow shop; scheduling; recursive functions; branch and bound method; sequence-dependent setup times; Mathematics Subject Classification: 90B35 1 Introduction The flow shop problem is a classical scheduling problem which has been intensively inivestigated in the literature. A set of n jobs has to be processed on a set of m machines in the same order. Often the permutation flow shop problem (PFSP) is considered, where on all machines the same job order has to be chosen. This means that one has to select one of the n! possible job permutations such that a certain optimization criterion is satisfied, e.g. the maximum completion time of a job. The PFSP has a number of practical applications in the industry. This paper presents an original method for describing several extensions of the PFSP. We describe an approach which is based on the use of recursive functions. The arguments of the recursive function are a pair (job number, machine number), and the calculated value is the completion time of the given job on the given machine. Subsequently, we consider three types of recursive functions: functions associated with a machine, functions that adjust processing time based on constraints, and functions that control the feasibility of a schedule. The structure of the superpositions of these functions is described. In total, this paper discusses six types of PFSP extensions that have not yet been considered as a single problem. The consideration of recursive functions in connection with scheduling problems is rather new. The paper [ 1 ] discusses the use of recursive functions to extend the PFSP with the predicate and and also in connection with job shop problems, where the jobs may have different machine routes. The applicability of recursive functions is determined by two of their main features. The first and main feature of a recursive function is that it is, by definition, calculated using some algorithm [ 2 , 3 ] . This distinguishes it from an analytical function. The same function can be calculated using several algorithms. This feature allows, when solving problems in scheduling theory, to localize a part of the algorithmic calculations in the body of a recursive function and make them basic objects for describing and solving certain problems. The second feature is the ability to define a recursive function through itself and other functions, which allows for complex structural calculations, for example on a precedence graph which, in another setting, are only possible using cyclic calculations. The applicability of recursive functions to scheduling problems is due to the fact that precedence relations are defined for them both between the machines and between the jobs (with a fixed order of jobs) [ 1 ] . Most of the problems considered in this paper are NP-hard, and exact solutions are possible only for small dimensions. Among the methods used to find approximate solutions, such as, for example, the ant colony (AC) method [ 4 ] or the simulated annealing (SA) [ 5 ] method, for optimizing a certain function, essentially only its computability is required. In [ 6 ] , the application of one exact and two approximate methods for solving PFSPs is investigated: branch and bound, ant colony, and simulated annealing. The problems are described by recursive functions and use the predicate and ; this model allows solving planning problems for certain types of assembly production. The precedence graphs for those problems are generated by a pseudo-random directed acyclic graph generator, which allows for a large number of generated statistics and calculated results. 80 tests were performed for 14, 100 and 200 jobs. The paper [ 6 ] also discusses a common SDST manufacturing problem with sequence-dependent setup times. This outline of this paper is as follows: In Section 2, the description of the PFSP and the definition of the precedence relation between the jobs and machines is given. The representation of the PFSP using recursive functions is considered in Section 3. In Section 4, the description of recursive functions of PFSP extensions and the structure of function superpositions is given. Section 5 introduces some typical objective functions and in Section 6, the description of a subset of recursive functions applicable to solving the PFSP and the properties of these functions are given. Section 7 presents the description of the branch and bound method for an extended PFSP and an example of a problem solution. Finally, Section 8 gives some concluding results. 2 Description of the flow shop problem class Consider the description of the PFSP [ 7 ] . Let {\cal J}=\{1,2,\dots,n\} be the set of jobs; {\cal M}=\{1,2,\dots,m\} be the set of machines arranged sequentially; P(n,m) be the matrix of the job completion times, where p_{j,k} is the processing time of job j on machine k . Figure 1: Example of a flow shop problem chain. The graph of the precedence relations of the machines for the single job (see Figure 1 ) is a simple chain in which the vertices are machines and the arcs define the precedence relationships between them. With a certain fixed order of jobs, this graph can be ”expanded”, and the precedence relationships between the jobs {\cal J}\times{\cal J} and between the machines {\cal M}\times{\cal M} (see Figure 2 ) can be defined. Figure 2: Example of an expanded graph for a flow shop problem. Each vertex of such a graph can be identified with a pair (job number, machine number). The vertical arcs define the precedence relationships between the jobs for a particular machine. The horizontal arcs define precedence relationships between the machines for a fixed job number. This graph is acyclic and has one start and one end vertex. The following assumptions hold for the FSP: 1. Assumptions about the jobs: (a) any job cannot be performed by more than one machine at the same time; (b) each job must be performed on each machine according to the given machine precedences; (c) any job is performed by the machine in the shortest possible time, depending on the order of the machines; (d) all jobs are equally important, meaning that there are no priorities, deadlines, or urgent jobs. 2. Assumptions about the machines: (a) no machine can perform more than one job at a time; (b) after the start of a processing, each job must be

Read the complete text