On the Recursive Representation of the Permutation Flow and Job Shop Scheduling Problems and Some Extensions

Boris Kupriyanov, Alexander Lazarev, Alexander Roschin and Frank Werner ()
Additional contact information
Boris Kupriyanov: V. A. Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, 117997 Moscow, Russia
Alexander Lazarev: V. A. Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, 117997 Moscow, Russia
Alexander Roschin: V. A. Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, 117997 Moscow, Russia
Frank Werner: Fakultät für Mathematik, Otto-von-Guericke-Universität Magdeburg, 39016 Magdeburg, Germany

Mathematics, 2025, vol. 13, issue 19, 1-28

Abstract: In this paper, we propose a formulation of the permutation flow and job shop scheduling problems using special recursive functions and show its equivalence to the existing classical formulation. Equivalence is understood in the sense that both ways of defining the problem describe the same set of feasible schedules for each pair of jobs and machine numbers. In this paper, the apparatus of recursive functions is used to describe and solve three problems: permutation flow shop; permutation flow shop with the addition of the ’and’ predicate extending the machine chain to an acyclic graph; and permutation job shop. The predicate ’and’ allows the description of the flow shop with assembly operation tasks. Recursive functions have a common domain and range. To calculate an optimal schedule for each of these three problems, a branch and bound method is considered based on a recursive function that implements a job swapping algorithm. The complexity of the optimization algorithm does not increase compared to the non-recursive description of the PFSP. This article presents some results for the calculation of optimal schedules on several test instances. It is expected that the new method, based on the description of recursive functions and their superposition, will be productive for formulating and solving some extensions of scheduling problems that have practical significance.

Keywords: flow shop; job shop; assembly operations; recursive functions; branch and bound method; scheduling (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/19/3185/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/19/3185/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:19:p:3185-:d:1764954

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().