Exact and Metaheuristic Approaches for the Production Leveling Problem

• URL: http://arxiv.org/abs/2006.08731v1
• Date: Mon, 15 Jun 2020 20:04:59 GMT
• Title: Exact and Metaheuristic Approaches for the Production Leveling Problem
• Authors: Johannes Vass, Marie-Louise Lackner, Nysret Musliu
• Abstract summary: This paper introduces a new problem in the field of production planning which we call the Production Leveling Problem. The task is to assign orders to production periods such that the load in each period and on each production resource is balanced, capacity limits are not exceeded and the orders' priorities are taken into account. A formal model of the problem is proposed and NP-hardness is shown by reduction from Bin Backing.
• Score: 5.510992382274775
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we introduce a new problem in the field of production planning which we call the Production Leveling Problem. The task is to assign orders to production periods such that the load in each period and on each production resource is balanced, capacity limits are not exceeded and the orders' priorities are taken into account. Production Leveling is an important intermediate step between long-term planning and the final scheduling of orders within a production period, as it is responsible for selecting good subsets of orders to be scheduled within each period. A formal model of the problem is proposed and NP-hardness is shown by reduction from Bin Backing. As an exact method for solving moderately sized instances we introduce a MIP formulation. For solving large problem instances, metaheuristic local search is investigated. A greedy heuristic and two neighborhood structures for local search are proposed, in order to apply them using Variable Neighborhood Descent and Simulated Annealing. Regarding exact techniques, the main question of research is, up to which size instances are solvable within a fixed amount of time. For the metaheuristic approaches the aim is to show that they produce near-optimal solutions for smaller instances, but also scale well to very large instances. A set of realistic problem instances from an industrial partner is contributed to the literature, as well as random instance generators. The experimental evaluation conveys that the proposed MIP model works well for instances with up to 250 orders. Out of the investigated metaheuristic approaches, Simulated Annealing achieves the best results. It is shown to produce solutions with less than 3% average optimality gap on small instances and to scale well up to thousands of orders and dozens of periods and products. The presented metaheuristic methods are already being used in the industry.

Related papers

• MAP: Low-compute Model Merging with Amortized Pareto Fronts via Quadratic Approximation [80.47072100963017]
  We introduce a novel and low-compute algorithm, Model Merging with Amortized Pareto Front (MAP) MAP efficiently identifies a set of scaling coefficients for merging multiple models, reflecting the trade-offs involved. We also introduce Bayesian MAP for scenarios with a relatively low number of tasks and Nested MAP for situations with a high number of tasks, further reducing the computational cost of evaluation.
  arXiv  Detail & Related papers  (2024-06-11T17:55:25Z)
• Mixed-model Sequencing with Stochastic Failures: A Case Study for Automobile Industry [0.0]
  In the automotive industry, the sequence of vehicles to be produced is determined ahead of the production day. This paper proposes a two-stage program for the mixed-model sequencing (MMS) problem with product failures.
  arXiv  Detail & Related papers  (2023-06-22T01:09:18Z)
• Leaving the Nest: Going Beyond Local Loss Functions for Predict-Then-Optimize [57.22851616806617]
  We show that our method achieves state-of-the-art results in four domains from the literature. Our approach outperforms the best existing method by nearly 200% when the localness assumption is broken.
  arXiv  Detail & Related papers  (2023-05-26T11:17:45Z)
• Concepts and Algorithms for Agent-based Decentralized and Integrated Scheduling of Production and Auxiliary Processes [78.120734120667]
  This paper describes an agent-based decentralized and integrated scheduling approach. Part of the requirements is to develop a linearly scaling communication architecture. The approach is explained using an example based on industrial requirements.
  arXiv  Detail & Related papers  (2022-05-06T18:44:29Z)
• Towards Standardizing Reinforcement Learning Approaches for Stochastic Production Scheduling [77.34726150561087]
  reinforcement learning can be used to solve scheduling problems. Existing studies rely on (sometimes) complex simulations for which the code is unavailable. There is a vast array of RL designs to choose from. standardization of model descriptions - both production setup and RL design - and validation scheme are a prerequisite.
  arXiv  Detail & Related papers  (2021-04-16T16:07:10Z)
• 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)
• 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)
• Exact and heuristic methods for the discrete parallel machine scheduling location problem [0.0]
  The problem consists in choosing the locations of $p$ machines among a finite set of candidates and scheduling a set of jobs on these machines. It is proposed a new arc-flow formulation, a column generation and three procedures that are evaluated through extensive computational experiments.
  arXiv  Detail & Related papers  (2020-06-09T00:10:18Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)
• Improving a State-of-the-Art Heuristic for the Minimum Latency Problem with Data Mining [69.00394670035747]
  Hybrid metaheuristics have become a trend in operations research. A successful example combines the Greedy Randomized Adaptive Search Procedures (GRASP) and data mining techniques.
  arXiv  Detail & Related papers  (2019-08-28T13:12:30Z)

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.