Comprehensive Benchmarking Environment for Worker Flexibility in Flexible Job Shop Scheduling Problems

• URL: http://arxiv.org/abs/2501.16159v1
• Date: Mon, 27 Jan 2025 15:56:12 GMT
• Title: Comprehensive Benchmarking Environment for Worker Flexibility in Flexible Job Shop Scheduling Problems
• Authors: David Hutter, Thomas Steinberger, Michael Hellwig,
• Abstract summary: In Production Scheduling, the Flexible Job Shop Scheduling Problem (FJSSP) aims to optimize a sequence of operations and assign each to an eligible machine with varying processing times. The resulting problem is called Flexible Job Shop Scheduling Problem with Worker Flexibility (FJSSP-W) This paper presents a collection of 402 commonly accepted FJSSP instances and proposes an approach to extend these with worker flexibility.
• Score: 0.0
• License:
• Abstract: In Production Scheduling, the Flexible Job Shop Scheduling Problem (FJSSP) aims to optimize a sequence of operations and assign each to an eligible machine with varying processing times. For integration of the workforce, each machine also requires a worker to be present to process an operation which additionally affects the processing times. The resulting problem is called Flexible Job Shop Scheduling Problem with Worker Flexibility (FJSSP-W). The FJSSP has been approached with various problem representations, including Mixed Integer Linear Programming (MILP), Constrained Programming (CP), and Simulation-based Optimization (SBO). In the latter area in particular, there exists a large number of specialized Evolutionary Algorithms (EA) like Particle Swarm Optimization (PSO) or Genetic Algorithms (GA). Yet, the solvers are often developed for single use cases only, and validated on a few selected test instances, let alone compared with results from solvers using other problem representations. While suitable approaches do also exist, the design of the FJSSP-W instances is not standardized and the algorithms are hardly comparable. This calls for a systematic benchmarking environment that provides a comprehensive set of FJSSP(-W) instances and supports targeted algorithm development. It will facilitate the comparison of algorithmic performance in the face of different problem characteristics. The present paper presents a collection of 402 commonly accepted FJSSP instances and proposes an approach to extend these with worker flexibility. In addition, we present a detailed procedure for the evaluation of scheduling algorithms on these problem sets and provide suitable model representations for this purpose. We provide complexity characteristics for all presented instances as well as baseline results of common commercial solvers to facilitate the validation of new algorithmic developments.

Related papers

• Federated Conditional Stochastic Optimization [110.513884892319]
  Conditional optimization has found in a wide range of machine learning tasks, such as in-variant learning tasks, AUPRC, andAML. This paper proposes algorithms for distributed federated learning.
  arXiv  Detail & Related papers  (2023-10-04T01:47:37Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  Combinatorial optimization (CO) problems are often NP-hard and out of reach for exact algorithms. GFlowNets have emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially. In this paper, we design Markov decision processes (MDPs) for different problems and propose to train conditional GFlowNets to sample from the solution space.
  arXiv  Detail & Related papers  (2023-05-26T15:13:09Z)
• Flexible Job Shop Scheduling via Dual Attention Network Based Reinforcement Learning [73.19312285906891]
  In flexible job shop scheduling problem (FJSP), operations can be processed on multiple machines, leading to intricate relationships between operations and machines. Recent works have employed deep reinforcement learning (DRL) to learn priority dispatching rules (PDRs) for solving FJSP. This paper presents a novel end-to-end learning framework that weds the merits of self-attention models for deep feature extraction and DRL for scalable decision-making.
  arXiv  Detail & Related papers  (2023-05-09T01:35:48Z)
• Decomposition Strategies and Multi-shot ASP Solving for Job-shop Scheduling [7.977161233209228]
  Job-shop Scheduling Problem (JSP) is a well-known and challenging optimization problem in which tasks sharing a machine are to be arranged in a sequence such that encompassing jobs can be completed as early as possible. In this paper, we investigate problem decomposition into time windows whose operations can be successively scheduled and optimized by means of multi-shot Answer Set Programming (ASP) solving.
  arXiv  Detail & Related papers  (2022-05-16T09:33:00Z)
• Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method [44.4747903763245]
  The Jobs shop Scheduling Problem (JSP) is a canonical optimization problem that is routinely solved for a variety of industrial purposes. The problem is NP-hard and computationally challenging even for medium-sized instances. This paper explores a deep learning approach to deliver efficient and accurate approximations to the problem.
  arXiv  Detail & Related papers  (2021-10-12T21:15:19Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together. The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively. Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
  arXiv  Detail & Related papers  (2021-03-10T03:16:12Z)
• Solving a Multi-resource Partial-ordering Flexible Variant of the Job-shop Scheduling Problem with Hybrid ASP [0.4511923587827302]
  We consider a Multi-resource Partial-ordering Flexible Job-shop Scheduling (MPF-JSS) problem. The resources are flexible and can perform one or more operations depending on their properties. Experiments conducted on a set of instances extracted from a medium-sized semiconductor fault analysis lab indicate that our approach can find schedules for 87 out of 91 considered real-world instances.
  arXiv  Detail & Related papers  (2021-01-25T15:21:32Z)
• A global-local neighborhood search algorithm and tabu search for flexible job shop scheduling problem [3.946442574906068]
  This work presents a new meta-heuristic algorithm called GLNSA (Global-local neighborhood search algorithm) The proposed algorithm is complemented with a tabu search that implements a simplified version of the Nopt1 neighborhood. Experiments carried out show a satisfactory performance of the proposed algorithm, compared with other results published in recent algorithms.
  arXiv  Detail & Related papers  (2020-10-23T23:08:51Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Metaheuristics for the Online Printing Shop Scheduling Problem [0.0]
  This real scheduling problem, that emerged in the nowadays printing industry, corresponds to a flexible job shop scheduling problem with sequencing flexibility. A local search strategy and metaheuristic approaches for the problem are proposed and evaluated. Numerical experiments with classical instances of the flexible job shop scheduling problem show that the introduced methods are also competitive when applied to this particular case.
  arXiv  Detail & Related papers  (2020-06-22T15:38:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.