# Single Machine Order Acceptance Scheduling with Periodic Energy Consumption Limits

Mariam Bouzid, Oussama Masmoudi, Alice Yalaoui

► To cite this version:

Mariam Bouzid, Oussama Masmoudi, Alice Yalaoui. Single Machine Order Acceptance Scheduling with Periodic Energy Consumption Limits. IFIP International Conference on Advances in Production Management Systems, Sep 2021, Nantes, France. pp.372-377, 10.1007/978-3-030-85874-2_39. hal-03350915

HAL Id: hal-03350915

https://hal.science/hal-03350915

Submitted on 15 Feb 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Single machine Order Acceptance Scheduling
with periodic energy consumption limits

Mariam Bouzid, Oussama Masmoudi, and Alice Yalaoui

Computer Laboratory and Digital Society (LIST3N), Troyes, France
{mariam.bouzid,oussama.masmoudi,alice.yalaoui}@utt.fr

**Abstract.** This work presents an Order Acceptance Scheduling (OAS) problem with the introduction of energy consumption limits at each period of the planning horizon. The objective is to maximize total profit of accepted orders while considering energy usage over time, in accordance with imposed deadlines. A time-indexed formulation is presented to tackle the investigated problem.

**Keywords:** Order Acceptance Scheduling · Energy consumption · Time-indexed.

## 1 Introduction

Resource depletion has become a major concern these past decades for both economic and environmental reasons. Standards, taxes and limits on resource use, are ones of many tools implemented by authorities to curb the current trend. Although, as stated in [11], new business opportunities are opened by these challenges and structural changes are required in the supply chain in the context of sustainability. This leads industrials to reconsider their rate of production at the operational level. During production, many levers can be taken into account, such as machine speed, shutdown mechanisms, among others. Monitoring energy consumption and costs, or carbon emissions during the production processes are useful indicators to mitigate impacts on the environment and to make substantial savings. Meanwhile, accepting or rejecting orders occurs in a plethora of manufacturing sectors when a company is limited by its facilities, client deadlines or in general by resources availability. Optimizing the production schedule is therefore essential to make a good balance between available production capacity and sales volume.

In this vein, this paper focuses on a capacity-constrained system by addressing an Order Acceptance Scheduling (OAS) problem with periodic energy consumption limits with the objective to maximize total profit. Section 2 presents a short literature review on resource-efficiency and energy-efficiency in scheduling problems with a focus on OAS problems. Section 3 gives a description of the proposed problem. Section 4 provides the solving approach and section 5 gives the preliminary results on a small benchmark. The final section features conclusions and perspectives to this work.
## 2 Related literature

Resource-efficiency and more globally resource management appeared at early stage of scheduling problem researches [1]. The characterization of resources in terms of availability and divisibility allow to cover a broad range of situations. Time-dependent resources, i.e. when the amount of resources varies over time, is for instance studied for an open shop and a parallel machine system in [13].

Resource management typically occurs during a project with dependent activities such as construction engineering, or manufacturing. In order to carry out a project at a lower cost while satisfying timing, labor, material, or equipment constraints, the Resource-Constrained Project Scheduling problem (RCPSP) [2] (and its variants) addresses this problem particularly well. On another side, financial scheduling problem insists on other interesting aspects of resources, in particular when they are assimilated to a stock (e.g. wages, raw materials) that can be replenished at different time of the horizon. Most of the studies on this topic provide solid complexity analysis and approximation schemes [6, 7]. Gafarov et al. [3] proved the NP-hardness of the single machine problem with non-renewable resources with the objective to minimize the makespan. They provide the optimal sequence to a particular polynomial case of the problem with the objective to minimize total tardiness. When it comes to energy, usually, efficiency is conceptualized by incorporating a specific criteria within the objective [4]. Therefore, total energy cost or consumption is minimized in numerous works including single machine and more complex systems. However, few researches address energy-efficiency by introducing dedicated constraints that differ from conventional resource constraints. For parallel machines, [10], minimized makespan with interval limits on energy consumption. They used two exact solving approaches, which are Branch and Bound and Benders decomposition, and a Tabu search to tackle this problem. In the meantime, Liao et al. [9] minimized both weighted completion times and weighted tardiness on a single machine with interval limits on energy consumption. They proposed an evolutionary algorithm for this multi-objective problem.

Introducing resource constraints is no exception in OAS, since it can be expected that limited resources force manufacturers to reconsider how much they can produce, avoiding losses as much as possible. For instance, [5] are the first to consider an OAS on a single machine with resource-constraints, rejecting orders if they cannot be completed within a predetermined time-window. The work of Kong et al. [8] presents an order acceptance scheduling problem with a global budget on energy use in a parallel machines system.

To the best of our knowledge, the OAS problem on a single machine with periodic resource consumption limits has not yet been tackled. This problem is interesting and appears when a resource consumed by production (such as energy) cannot be stored and is different from a period to another. This typically appears in period of high energy consumption.
## 3 Problem description

This paper investigates an Order Acceptance scheduling problem on a single non-preemptive machine with energy consumption limits at each period. The objective is to maximize total profit while satisfying periodic energy consumption limits. This problem is NP-hard since the OAS problem on a single machine, maximizing the total profit is NP-hard in its basic form [12].

As in [13], in this problem, the resource is renewable, that is, a energy unit available at time $t$ shall be consumed at time $t$ but can not be saved for later. The availability of the resource at time $t + 1$ does not depend on the amount consumed at or before time $t$, unlike financial scheduling problem. Energy is thus available in time-dependent quantities, i.e. their availability changes over time. Each order is defined by its processing time $p_j$, its deadline $\bar{d}_j$, its unitary power consumption $e_j$ (kW) and its revenue $f_j$.

The following assumptions are formulated:

- The energy consumed by an order remains constant during the totality of its production.

- Preemption is not allowed.

- The manufacturer earns the totality of the revenue of an order $j$ if it can be scheduled completely before its deadline.

The horizon is split into unitary slots $t = 1, \dots, T$ each characterized by an energy limit $E_t$. The length of the horizon $T$ is defined by the maximum of the deadlines.

For illustration purpose, let's take an example of $n = 5$ orders where $p = [8, 3, 4, 4, 3]$, $\bar{d} = [25, 16, 9, 21, 9]$, $e = [3.5, 4, 3.5, 3.5, 2]$ and $f = [15, 10, 10, 5, 10]$. Assume that orders 2 and 4 are rejected.

<figure><img src="image_3.png" /><figcaption>Fig. 1. An example with $n = 5$ orders.</figcaption></figure>
In fig. 1, the bar chart represents the amount of available energy $E_t$ at each period $t = 1, \dots, T$. The sequence is represented by a Gantt diagram below. An order $j$ is represented by two components : its energy consumption $e_j$ in height and its processing time $p_j$ in width.

## 4 Solving approach

A time-indexed On/Off formulation is used to model the proposed problem. In this formulation, the binary decision variables $x_{jt} = 1$ refer to the production of a unit of order $j$ at time $t$ (or not $x_{jt} = 0$). Moreover, the binary decision variables $a_j$ equals 1 if the order $j$ is accepted, 0 otherwise. The problem is formulated as a Mixed Integer Linear Program as follows.

$$ \text{maximize} \sum_{j=1}^{n} a_j f_j \qquad (1) $$

subject to

$$ \sum_{j=1}^{n} x_{jt} \le 1 \quad t = 1, \dots, T \qquad (2) $$

$$ \sum_{t=1}^{\bar{d}_j} x_{jt} = p_j a_j \quad j = 1, \dots, n \qquad (3) $$

$$ \sum_{t'=1}^{t-p_j} x_{jt'} + \sum_{t'=t+p_j}^{\bar{d}_j} x_{jt'} \le p_j(1-x_{jt}) \quad j=1, \dots, n, \quad t=p_j+1, \dots, \bar{d}_j \qquad (4) $$

$$ \sum_{j=1}^{n} e_j x_{jt} \le E_t \quad t = 1, \dots, T \qquad (5) $$

$$ \sum_{t=\bar{d}_j+1}^{T} x_{jt} = 0 \quad j = 1, \dots, n \qquad (6) $$

The objective (1) is the maximization of the sum of the revenue of the accepted orders. Constraints (2) ensure that the machine can either produce or do nothing. Constraints (3) state that an accepted order must be processed $p_j$ time units within its time-window $r_j, \dots, \bar{d}_j$. Constraints (4) guarantee non-preemption by forcing the continuity of the decision variables $x_{jt}$. If at time period $t$ order $j$ is produced ($x_{jt} = 1$), the constraints exclude production $p_j$ units before and after $t$, i.e in periods $1, \dots, t-p_j$ and $t+p_j, \dots, \bar{d}_j$. Constraints (5) are the periodic energy consumption limits, imposing that a unit of production of an order at time $t$ does not exceed $E_t$, the available energy at time $t$. Constraints (6) prevent any order $j$ to be produced after its deadline $\bar{d}_j$.
# 5 Preliminary results

The tested instances have been randomly generated with diverse number of orders $n = 10, 15, 25, 50, 100, 5$ for each value of $n$. Processing times and revenues are generated from the uniform distribution $p_j, f_j \sim U(1, 20)$. The unitary power consumption is computed as follows: $e_j \sim U(1, f_j) \times \frac{1}{2}$. The values of the deadlines are determined by $\bar{d}_j = U(p_j, p_T)$ with $p_T = \sum_{j=1}^{n} p_j$. The energy consumption limits over time are randomly generated with $E_t \sim U(1, 10)$ for all $t = 1, \dots, T$. The value of the energy consumption limits are the same across the benchmark. The tests have been performed on a PC with Intel i5 2GHz CPU processor and 4GB RAM. The provided model is written in the IBM CPLEX Solver v12.9. Solving time is limited to 3600 seconds.

<table><caption>**Table 1.** Computational results.</caption><thead><tr><th>n</th><th>cpū</th><th>gap̄</th><th>% acc</th></tr></thead><tbody><tr><td>10</td><td>0.03</td><td>0</td><td>0.22</td></tr><tr><td>15</td><td>0.07</td><td>0</td><td>0.24</td></tr><tr><td>25</td><td>0.55</td><td>0</td><td>0.28</td></tr><tr><td>50</td><td>675</td><td>0</td><td>0.38</td></tr><tr><td>100</td><td>3600</td><td>53</td><td>0.32</td></tr></tbody></table>

Table 1 presents the results obtained by the solver. Each line represents 5 instances with varying number of orders. The average solving time (in seconds) and the average gap (CPLEX relative Gap in %) is reported for each batch of instances. Finally, the average proportion of accepted orders is indicated (in %). The model performs well for small to medium instance size with less than a second to optimally solve the instances. As can be seen, from $n = 50$, the average cpu time sharply increases. With $n = 100$ orders, the model cannot find some feasible solutions (3/5 are feasibles) with poor solution quality.

# 6 Conclusion and perspectives

In this paper, the OAS problem on a single machine with periodic energy consumption limits is studied. A time-indexed model with $O(nT)$ constraints and $O(nT)$ decision variables is used to solve this problem. Since the objective is the maximization of total profit with time-dependent resource constraints, the time-indexed model is a purposeful choice as it exploits to its benefit the time dependency of the investigated problem. A comparison between the proposed time-indexed model and a classical formulation using completion times shall be done. The development of dedicated exact methods is planned in the future work due to solver limitations. A special focus will be made on finding dedicated cuts, bounds and properties of the problem. Moreover, the formalisation of diverse
type of constraints that make sense in the context of energy-efficient scheduling must be performed. Global, cumulative and rolling-window constraints must be studied with a careful examination of mathematical properties and a complexity analysis for each of the problem variants. Preliminaries results will be presented on this occasion.

## References

1. Błażewicz, J.: Scheduling under resource constraints: Deterministic models. JC Baltzer (1986)

2. Brucker, P., Drexl, A., Mo, R., Pesch, E.: Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research p. 39 (1999)

3. Gafarov, E.R., Lazarev, A.A., Werner, F.: Single machine scheduling problems with financial resource constraints: Some complexity results and properties. Mathematical Social Sciences (1), 7–13 (Jul 2011)

4. Gao, K., Huang, Y., Sadollah, A., Wang, L.: A review of energy-efficient scheduling in intelligent production systems. Complex & Intelligent Systems 6(2), 237–249 (Jul 2020)

5. Garcia, C.: Resource-constrained scheduling with hard due windows and rejection penalties. Engineering optimization 48(9), 1515–1528 (2016)

6. Györgyi, P., Kis, T.: Minimizing total weighted completion time on a single machine subject to non-renewable resource constraints. Journal of Scheduling 22(6), 623–634 (Dec 2019)

7. Györgyi, P., Kis, T.: New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints. arXiv:2004.00972 [math] (Apr 2020), arXiv: 2004.00972

8. Kong, M., Pei, J., Liu, X., Lai, P.C., Pardalos, P.M.: Green manufacturing: Order acceptance and scheduling subject to the budgets of energy consumption and machine launch. Journal of Cleaner Production 248, 119300 (Mar 2020)

9. Liao, X., Zhang, R., Chiong, R.: Multi-objective optimization of single machine scheduling with energy consumption constraints. In: 2017 IEEE Symposium Series on Computational Intelligence (SSCI). pp. 1–8. IEEE, Honolulu, HI (Nov 2017)

10. Módos, I., Šúcha, P., Hanzálek, Z.: Algorithms for robust production scheduling with energy consumption limits. Computers & Industrial Engineering 112, 391–408 (Oct 2017)

11. O'Brien, M., Fischer, S., Schepelmann, P., Bringezu, S.: Resource efficiency in european industry

12. Palakiti, V.P., Mohan, U., Ganesan, V.K.: Order acceptance and scheduling: overview and complexity results p. 18

13. Tautenhahn, T., Woeginger, G.J.: Unit-time scheduling problems with time dependent resources. Computing 58(2), 97–111 (Jun 1997)