Propagation and Branching Strategies for Job Shop Scheduling Minimizing the Weighted Energy Consumption

Andreas Bley () and Andreas Linß ()
Additional contact information
Andreas Bley: Institut für Mathematik, Universität Kassel
Andreas Linß: Institut für Mathematik, Universität Kassel

Chapter Chapter 68 in Operations Research Proceedings 2022, 2023, pp 573-580 from Springer

Abstract: Abstract We consider a job shop scheduling problem with time windows, flexible energy prices, and machines whose energy consumption depends on their operational state (offline, ramp-up, setup, processing, standby or ramp-down). The goal is to find a valid schedule that minimizes the overall energy cost. To solve this problem to optimality, we developed a branch-and-bound algorithm based on a time-indexed integer linear programming (ILP) formulation, which uses binary variables that describe blocks spanning multiple inactive periods on the machines. In this paper, we discuss the propagation and branching schemes used in that algorithm. The strategies, which are specifically tailored for energy related machine scheduling problems, primarily aim to determine and sharpen the activity profiles of the machines (and thus reduce the number of the inactive block variables) and address the workload profile of the tasks with lower priority. Computational experiments validate the efficiency of those techniques.

Keywords: Integer programming; Machine scheduling; Presolving; Branch and bound (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:lnopch:978-3-031-24907-5_68

Ordering information: This item can be ordered from
http://www.springer.com/9783031249075

DOI: 10.1007/978-3-031-24907-5_68

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().