Exact methods for the oven scheduling problem
From MaRDI portal
Abstract: The Oven Scheduling Problem (OSP) is a new parallel batch scheduling problem that arises in the area of electronic component manufacturing. Jobs need to be scheduled to one of several ovens and may be processed simultaneously in one batch if they have compatible requirements. The scheduling of jobs must respect several constraints concerning eligibility and availability of ovens, release dates of jobs, setup times between batches as well as oven capacities. Running the ovens is highly energy-intensive and thus the main objective, besides finishing jobs on time, is to minimize the cumulative batch processing time across all ovens. This objective distinguishes the OSP from other batch processing problems which typically minimize objectives related to makespan, tardiness or lateness. We propose to solve this NP-hard scheduling problem via constraint programming (CP) and integer linear programming (ILP) and present corresponding models. For an experimental evaluation, we introduce a multi-parameter random instance generator to provide a diverse set of problem instances. Using state-of-the-art solvers, we evaluate the quality and compare the performance of our CP- and ILP-models. We show that our models can find feasible solutions for instances of realistic size, many of those being provably optimal or nearly optimal solutions. Finally, we derive theoretical lower bounds on the solution cost of feasible solutions to the OSP; these can be computed within a few seconds. We show that these lower bounds are competitive with those derived by state-of-the-art solvers.
Recommendations
- Minimizing makespan on a single burn-in oven with job families and dynamic job arrivals
- Minimizing makespan on a single burn-in oven in semiconductor manufacturing
- A new MIP model for parallel-batch scheduling with non-identical job sizes
- Tabu search methods for scheduling a burn-in oven with non-identical job sizes and secondary resource constraints
- Scheduling a burn-in oven with non-agreeable release times and due dates
Cites work
- A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes
- A constraint programming approach for a batch processing problem with non-identical job sizes
- A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families
- A new MIP model for parallel-batch scheduling with non-identical job sizes
- A survey of scheduling with parallel batch (p-batch) processing
- Comparison of multi-objective optimization methodologies for engineering applications
- Constraint and integer programming in OPL
- CP and hybrid models for two-stage batching and scheduling
- Efficient Algorithms for Scheduling Semiconductor Burn-In Operations
- IBM ILOG CP optimizer for scheduling. 20+ years of scheduling with constraints at IBM/ILOG
- Introduction to the theory of voting
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Scheduling a batching machine
- Scheduling a single batch processing machine with non-identical job sizes
- Scheduling batch processing machines with incompatible job families
- Scheduling with batching: A review
- Trade-off analysis approach for interactive nonlinear multiobjective optimization
Cited in
(3)- Instance space analysis and algorithm selection for a parallel batch scheduling problem
- Population-based iterated local search for batch scheduling on parallel machines with incompatible job families, release dates, and tardiness penalties
- Multi-neighborhood simulated annealing for the oven scheduling problem
This page was built for publication: Exact methods for the oven scheduling problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6049438)
