# Approximation Algorithms for Job Scheduling with Reconfigurable Resources

Pierre Bergé  Université Clermont-Auvergne, CNRS, Mines de Saint-Etienne,
Clermont-Auvergne-INP, LIMOS, 63000 Clermont-Ferrand, France  Mari
Chaikovskaia  IMT Atlantique, LS2N, UMR CNRS 6004, F-44307 Nantes, France
Jean-Philippe Gayon  Université Clermont-Auvergne, CNRS, Mines de Saint-
Etienne, Clermont-Auvergne-INP, LIMOS, 63000 Clermont-Ferrand, France  Alain
Quilliot  Université Clermont-Auvergne, CNRS, Mines de Saint-Etienne,
Clermont-Auvergne-INP, LIMOS, 63000 Clermont-Ferrand, France

###### Abstract

We consider here the Multi_Bot problem for the scheduling and the resource
parametrization of jobs related to the production or the transportation of
different products inside a given time horizon. Those jobs must meet known in
advance demands. The time horizon is divided into several discrete identical
periods representing each the time needed to proceed a job. The objective is
to find a parametrization and a schedule for the jobs in such a way they
require as less resources as possible. Though this problem derived from the
applicative context of reconfigurable robots, we focus here on fundamental
issues. We show that the resulting strongly NP-hard Multi_Bot problem may be
handled in a greedy way with an approximation ratio of $4/3$.

Keywords : Reconfiguration, Scheduling, Approximation

##  1 Introduction

In many industrial contexts, automatized production must adapt itself to a
fast evolving demand of a large variety of customized products. One achieves
such a flexibility requirement through the notion of reconfiguration. Once an
operation is performed, related either to the production of some good or to
its transportation, one may redesign the infrastructure that supported this
operation by adding, removing or replacing some atomic components, or by
modifying the links that connect those components together. Those components
may be hardware (robots, instruments), software or human resources. They
behave as renewable resources [2, 3, 11] and move inside the production area
in order to fit, during a given production cycle, with current
production/transportation needs. Depending on the way one assigns those
resources to a given operation, one may not only achieve this operation but
also speed it, increase its throughput or lessen its cost, as in the multi-
modal Resource Constrained Project Scheduling Problem [2].

We consider the following scheduling problem with reconfigurable resources.
Several types of jobs (e.g. production operations, transportation tasks) have
to be processed by a set of identical resources (e.g. workers, robots,
processors) over a discrete time horizon in order to achieve a certain demand.
Assigning a number $p$ of resources to some job of type $k$ gives a certain
production $c_{pk}$: all production values, called capacities, are given as
inputs. In each time period, teams of resources must be formed to process
jobs. A resource which is used to perform some type of job $k$ at period $t$
may be employed for another type of job $k^{\prime}\neq k$ in the next period
$t+1$. The objective is to determine the minimum number of resources needed to
obtain a certain production for each type of job. This problem is called
Multi_Bot and is strongly NP-hard [6].

It has been firstly introduced in a warehouse logistics context [7] in
collaboration with the MecaBoTix company [15] which designs reconfigurable
mobile robots. In this application, resources are mobile robots and jobs
consist in moving loads of various types, such as pallets or boxes. Those
robots are capable of aggregating into a cluster to form poly-robots that can
adapt to the type of product (size/mass) and navigate independently in
environments such as warehouses, production sites or construction sites. Other
applications can be found in the automotive industry where the resources are
workers and the processing time for a task in the assembly line depends on the
number of workers assigned to it [1].

From a theoretical point of view, Multi_Bot is strongly related to some
classical scheduling problems of the literature. A very well-known one is
Identical-machines scheduling (IMS), where the objective is to pack items into
a set of identical boxes while minimizing the size of the most filled box
[10]. The standard scheduling notation of IMS is $P||C_{\max}$. Its high
multiplicity variant, denoted by $P|HM(n)|C_{\max}$, encodes as binary inputs
the number of items with the same size [4]. These two scheduling problems have
been widely studied in terms of approximation and parameterized complexity [5,
8, 12, 13, 14, 16, 17]. Problem $P|HM(n)|C_{\max}$, when the item sizes are
polynomially bounded, is a special case of Multi_Bot: consider that any type
of job $k$ correspond to some item size and can be performed only by a
specific number of resource $p_{k}$, the demands of jobs of type $k$
correspond to the high-multiplicity coefficients of the related items. In this
article, we will use a heuristic of IMS as a sub-routine of our algorithm.

The main result of this paper is the presentation of a polynomial-time
$\frac{4}{3}$-approximation algorithm for Multi_Bot. The impact of this
contribution is, in our opinion, twofold. On one hand, we provide, for
industrial applications such as MecaBotiX robots, a fast and efficient
heuristic with the strict guarantee that it will not fail on pathological
instances more than 33% over the optimum. On the other hand, we extend the
theoretical knowledge on approximability of scheduling problems, showing that
a generalization of $P|HM(n)|C_{\max}$ admits a constant approximation ratio.

The paper is organized as follows. In Section 2, we detail the Multi_Bot
problem, remind its ILP formulation and introduce the notions of schedule and
packing. Next we provide in Section 3 the definition of Identical-machines
scheduling (IMS) problem as well as some preliminary observations on the
optimum solutions of Multi_Bot. Section 4 is devoted to the description of our
approximation algorithm. This algorithm relies on a polynomial time dynamic
programming algorithm that solves Multi_Bot when the periods are merged into a
single macro-period: this is described in Section 5.

##  2 Problem description and notations

We consider a set of identical resources (for instance robots, workers, etc)
which cooperate in order to process different types of jobs. A $p$-resource is
a configuration which makes $p$ resources cooperate on the same job. For
example, in robotics, it models the fact that $p$ elementary robots can
assemble together in order to transport heavy loads. A maximum of $P$
resources may cooperate. The set of configurations is thus $\mathcal{P}$ =
{1,…, $P$}. There are $K$ job types and let $\mathcal{K}=\\{1,\ldots,K\\}$.
The demand for type $k$ of jobs is denoted by $d_{k}$ for every type
$k\in\mathcal{K}$, and $d_{\mbox{\scriptsize{max}}}$ is the maximum demand.
Given a job of type $k$, there is at least one value $p$ such that a
$p$-resource is able to process a job of type $k$.

All tasks must be executed within a discrete time horizon
$\mathcal{T}=\\{1,\ldots,T\\}$. At the beginning of each period
$t\in\mathcal{T}$, the resources may be reconfigured in order to provide us
with numerous configurations which perform jobs for period $t$. During a given
period $t$, a $p$-resource can deal with only a single type $k\in\mathcal{K}$,
and its production is given by the capacity $c_{pk}$. Our purpose is to
minimize the number of resources involved into the whole process. If $H_{t}$
denotes the number of active resources during period $t$, then the number of
resources necessary to achieve the whole process is
$H=\max\limits_{t\in\mathcal{T}}H_{t}$. Let Multi_Bot refer to this
optimization problem.

###  2.1 ILP formulation for Multi_Bot

More formally, we provide in Problem 1 the integer linear programming (ILP)
formulation of Multi_Bot. We denote by $x_{pkt}$ the decision variable
representing the number of jobs of type $k$ performed in configuration $p$ at
period $t$.

Constraint (2) means that we must have a sufficient total capacity to satisfy
demand $d_{k}$. Quantity
$\sum_{t\in\mathcal{T}}\sum_{p\in\mathcal{P}}c_{pk}\cdot x_{pkt}$ represents
the maximum number of jobs of type $k$ that can be processed over the horizon,
given the $x_{pkt}$. Constraint (3) means that the number of required
resources in period $t$ can be written as $H_{t}$ = $\sum_{p,k}p\cdot
x_{pkt}$. Constraint (4) means that $H$, the number of resources necessary to
achieve the whole process, must be greater than or equal to every $H_{t}$.
Constraint (5) recalls that all decision variables are non negative integers.

Figure 1 illustrates an optimal solution (i.e. which minimizes $H$) for the
following instance of Multi_Bot. There are two types of jobs ($K=2$) and three
periods ($T=3$). The maximum size of a performed job is $P=5$. The demands are
$d_{1}=13$ and $d_{2}=10$. The capacities for jobs of type 1 are $c_{11}=1$
and $c_{21}=4$. The demand $d_{1}=13$ is achieved as the schedule contains
three $2$-resources (total production 12) and one $1$-resource (production 1)
handling jobs of type $k=1$. The capacities for jobs of type 2 are linear in
$p$: for any $1\leq p\leq P$, $c_{p2}=p$. One can check the demand for $k=2$
is also reached. Furthermore, it is not possible to find a solution which
achieves $H=5$.

######  Problem 1 (Multi_Bot).

Input:
$\displaystyle\mathcal{K}=\left\\{1,\ldots,K\right\\},\mathcal{P}=\left\\{1,\ldots,P\right\\}$
$\displaystyle\mathcal{T}=\left\\{1,\ldots,T\right\\}$
$\displaystyle\emph{Capacities}~{}(c_{pk})_{\begin{subarray}{c}p\in\mathcal{P}\\\
k\in\mathcal{K}\end{subarray}}$
$\displaystyle\emph{Demands}~{}(d_{k})_{k\in\mathcal{K}}$ Objective:
$\displaystyle\emph{minimize}\,\,H$ (1) subject to:
$\displaystyle\sum_{t\in\mathcal{T}}\sum_{p\in\mathcal{P}}c_{pk}\cdot
x_{pkt}\geq d_{k}$ $\displaystyle\forall k\in\mathcal{K}$ (2) $\displaystyle
H_{t}=\sum_{k\in\mathcal{K}}\sum_{p\in\mathcal{P}}p\cdot x_{pkt}$
$\displaystyle\forall t\in\mathcal{T}$ (3) $\displaystyle H\geq H_{t}$
$\displaystyle\forall t\in\mathcal{T}$ (4) $\displaystyle
x_{pkt},H\in\mathbb{N}$ $\displaystyle\forall
k\in\mathcal{K},p\in\mathcal{P},t\in\mathcal{T}$ (5)

###  2.2 Schedules and packings

A solution of the Multi_Bot problem is thus a vector of size $PKT$:

$\mathbf{x}=(x_{pkt})_{\begin{subarray}{c}p\in\mathcal{P}\\\
k\in\mathcal{K}\\\ t\in\mathcal{T}\end{subarray}}$

In the remainder, we abuse notation when the context is clear: the same vector
could be denoted implicitly by $(x_{pkt})_{p,k,t}$ to gain some space. Also,
notations $x_{pkt}$ and $x_{p,k,t}$ refer to the same value.

Figure 1: An example of schedule $\mathbf{x}=(x_{pkt})_{p,k,t}$ with
$H=\max_{t}H_{t}=6$, meaning that at most $6$ resources are used per period.

The input size of Multi_Bot is $O\left(T+KP(\log
c_{\mbox{\scriptsize{max}}}+\log d_{\mbox{\scriptsize{max}}})\right)$.
Concretely, values $K,P,T$ can be seen as combinatorial inputs while demands
and capacities are numerical values. Hence, values $c_{pk}$ and $d_{k}$ might
be exponential in the input size, but also $x_{pkt}$, $H_{t}$ and $H$.
However, observe that the size of a solution $\mathbf{x}$ is polynomial in the
input size. We call such a solution a schedule of the Multi_Bot instance.

Given an instance of Multi_Bot,

  * •

let $H^{*}$ denote the optimum value for the evaluation function $H$,

  * •

let $\mathbf{x}^{*}=\left(x_{pkt}^{*}\right)_{p,k,t}$ be a schedule reaching
this optimum.

In comparison with a schedule $\mathbf{x}$ which is a vector with $KPT$
values, a packing $\bm{\pi}=(x_{pk})_{\begin{subarray}{c}p\in\mathcal{P}\\\
k\in\mathcal{K}\end{subarray}}$ represents the schedule of jobs of type $k$ by
$p$-resources, independently from any time consideration. For example, it can
be used to describe the production process during one specific period. This is
a vector with $KP$ values. Given some schedule $\mathbf{x}=(x_{pkt})_{p,k,t}$,
its associated packing is simply given by all values
$\sum_{t\in\mathcal{T}}x_{pkt}$, for all $p\in\mathcal{P},k\in\mathcal{K}$. In
particular, the packing associated with the optimal schedule $\mathbf{x}^{*}$
is denoted by $\bm{\pi}^{*}$ :

$\bm{\pi}^{*}=\left(\sum_{t\in\mathcal{T}}x_{pkt}^{*}\right)_{\begin{subarray}{c}p\in\mathcal{P}\\\
k\in\mathcal{K}\end{subarray}}$

We pursue with the definition of measures for both schedules and packings.

######  Definition 1 (Volume).

The _volume_ of a packing is the total number of resources involved in this
packing. Formally, for $\bm{\pi}=(x_{pk})_{p,k}$,

$\emph{vol}(\bm{\pi})=\sum_{k\in\mathcal{K}}\sum_{p\in\mathcal{P}}p\cdot
x_{pk}$

For the sake of simplicity, we also use this notion for schedules. The volume
of a schedule $\mathbf{x}$ is the volume of its associated packing, i.e.
$\sum_{p,k,t}p\cdot x_{pkt}$.

######  Definition 2 (Maximum).

The maximum of a packing $\bm{\pi}$ is the maximum $p\in\mathcal{P}$ such that
some $x_{pk}$ is non-zero. Formally,

$\max(\bm{\pi})=\max\left\\{p\in\mathcal{P}:x_{pk}>0~{}\mbox{for
some}~{}k\right\\}$

.

Eventually, we define another measure on packings that we will use in our
approximation algorithm: the scale.

######  Definition 3 (Scale).

Given some integer parameter $\lambda$, let us call the _big configurations_
the $p$-resources with $p>\frac{2\lambda}{3}$ and the _medium configurations_
the $p$-resources with $\frac{\lambda}{3}<p\leq\frac{2\lambda}{3}$. Naturally,
the _small configurations_ refer to $p\leq\frac{\lambda}{3}$. We define the
$\lambda$-_scale_ as the number of jobs performed with big configurations in
packing $\bm{\pi}$ plus half the number of jobs performed with medium
configurations in $\bm{\pi}$. It is a half-integer:

$\mbox{scale}_{\lambda}(\bm{\pi})=\sum_{k\in\mathcal{K}}\sum_{p>\frac{2\lambda}{3}}x_{pk}+\frac{1}{2}\sum_{k\in\mathcal{K}}\sum_{\frac{\lambda}{3}<p\leq\frac{2\lambda}{3}}x_{pk}$
(6)

Given a solution $\mathbf{x}$ of Multi_Bot using $H$ resources, its associated
packing $\bm{\pi}$ has a limited $H$-scale. Indeed, looking at how much medium
or big configurations a period can contain, we see that it has at most either
one big configuration or two medium configurations. For example, a period
cannot contain both a big and a medium configuration, by definition. Hence,
$\mbox{scale}_{\lambda}(\bm{\pi})\leq T$.

As an example, for the packing $\bm{\pi}$ associated to the schedule proposed
in Figure 1, we have $\mbox{vol}(\bm{\pi})=17$, $\max(\bm{\pi})=4$ and
$\mbox{scale}_{5}(\bm{\pi})=1+4\cdot\frac{1}{2}=3$.

##  3 Preliminaries

###  3.1 Approximation algorithms

Unfortunately, Multi_Bot is strongly NP-complete for the general case because
it can be reduced from Bin Packing [6]. Consequently, assuming P$\neq$NP,
there is no polynomial-time exact algorithm for Multi_Bot, even if the
numerical values are supposed to be polynomially-bounded by the input size. A
very natural question is thus the approximability of this problem.

An $r$-approximation algorithm, $r\geq 1$, for Multi_Bot is a polynomial-time
algorithm which outputs a solution $\mathbf{x}=(x_{pkt})_{p,k,t}$ such that:

$H=\max\limits_{t\in\mathcal{T}}\left(\sum\limits_{k\in\mathcal{K}}\sum\limits_{p\in\mathcal{P}}p\cdot
x_{pkt}\right)\leq r\cdot H^{*}$

Approximation algorithms offer the guarantee that the number of resources used
by the solution returned is at most a linear function of the optimum.

###  3.2 Identical-machines scheduling

We recall the definition and some results related to a well-known problem in
operations research: Identical-machines scheduling [10]. This problem can be
seen as the optimization of Bin Packing by the capacities, where the number of
boxes is fixed. In the scheduling framework, IMS corresponds to $P||C_{\max}$.
Its objective is to assign a set of $n$ tasks given with their processing
times to $m$ identical machines such that the makespan is minimized. To
distinguish IMS with Multi_Bot, we will use a slightly different syntax.
Formally, we are given a set of items $\mathcal{I}=\\{1,\cdots,n\\}$ and a set
of boxes $\mathcal{B}=\left\\{1,\ldots,m\right\\}$. An item $i$ has a certain
size $s_{i}$. The objective is to pack all items into the boxes such that the
total size packed inside the different boxes is balanced. More precisely, we
aim at minimizing the size of the most filled box.

######  Problem 2 (Identical-machines scheduling (IMS)).

Input: $\displaystyle\emph{Items}~{}\mathcal{I}=\left\\{1,\ldots,n\right\\},$
$\displaystyle\emph{Boxes}~{}\mathcal{B}=\left\\{1,\ldots,m\right\\}$
$\displaystyle\emph{Sizes}~{}\left\\{s_{i}\right\\}_{i\in\mathcal{I}}$
Objective: $\displaystyle\emph{minimize}\,\,H$ (7) subject to:
$\displaystyle\sum_{j\in\mathcal{B}}x_{ij}=1$ $\displaystyle\forall
i\in\mathcal{I}$ (8) $\displaystyle H_{j}=\sum_{i\in\mathcal{B}}p_{i}\cdot
x_{ij}$ $\displaystyle j\in\mathcal{B}$ (9) $\displaystyle H\geq H_{j}$
$\displaystyle j\in\mathcal{B}$ (10) $\displaystyle
x_{ij}\in\left\\{0,1\right\\}$ $\displaystyle i\in\mathcal{I},j\in\mathcal{B}$
(11)

Observe that the minimization function of Multi_Bot and IMS are similar: in
both problems, we aim at minimizing a certain “volume” of the jobs/items which
have been put into the most filled box/period. Naturally, we will try in the
remainder to reduce - in some sense - instances of Multi_Bot into instances of
the well-known problem IMS. There is a natural correspondence between packings
and instances of IMS, since each $p$-resource perfoming a job $k$ in
$\bm{\pi}$ can be seen as an item of size $p$. Said differently, for any
$p\in\mathcal{P}$, the $\sum_{k}x_{pk}$ resources present in packing
$\bm{\pi}$ can be converted into $\sum_{k}x_{pk}$ items of size $p$.

Given an IMS instance $\mathcal{J}$, we define:

  * •

its volume $\mbox{vol}(\mathcal{J})$ as the total size of its items, i.e.
$\mbox{vol}(\mathcal{J})=\sum_{i\in\mathcal{I}}s_{i}$,

  * •

its maximum as the maximum item size:
$\max(\mathcal{J})=\max_{i\in\mathcal{I}}s_{i}$.

A heuristic of IMS will be used as a sub-routine for our approximation
algorithm dedicated to Multi_Bot. It is called Longest-processing-time-first
(Lpt-first) [10]. Its description is relatively simple: first sort the items
by decreasing order of their sizes (the largest size comes first), second put
the items into the boxes following this order. The filling must satisfy the
following rule: we always fill the box with the largest empty space, or said
differently the least filled box. Figure 2 shows the packing obtained with
Lpt-first for a certain instance. Graham showed that Lpt-first is a
$\frac{4}{3}$-approximation algorithm [10]. In addition to offering a small
approximation ratio, Lpt-first is a fast algorithm: it runs only in $O(n(\log
m+\log n))$.

Figure 2: Output of Lpt-first with item sizes $(5,3,3,3,2,2,1)$

In the literature, IMS admits other approximation algorithms, such as Multifit
[8] which has a ratio $\frac{13}{11}$, proven by Yue [18]. Hochbaum and
Schmoys proposed a PTAS [12] and we know that IMS does not admit a FPTAS since
it is strongly NP-complete [9]. In the remainder, despite the existence of
smaller approximation ratios, we focus only on the Lpt-first algorithm since
it allows us to identify an approximation of Multi_Bot with our framework.

###  3.3 Optimal configurations

We provide a crucial observation for Multi_Bot which will help us designing
efficient algorithms in the remainder. This is based on the notion of optimal
configuration described below.

######  Definition 4 (Optimal configuration for $k\in\mathcal{K}$).

For any $k\in\mathcal{K}$, let $p_{0}(k)$ be the _optimal configuration_ for
jobs of type $k$, i.e. the configuration $p\in\mathcal{P}$ which is the most
efficient in terms of resources. In brief,

$p_{0}(k)=\operatorname*{argmax}_{p\in\mathcal{P}}\frac{c_{pk}}{p}$

For any optimum solution $\mathbf{x}^{*}$ of Multi_Bot, given some type $k$ of
job, the number $x_{p_{0}(k),k,t}^{*}$ of $p_{0}(k)$-resources used at each
period $t$ is potentially very large (exponential in the input size). However,
we know that the number of $p$-resources used, with $p\neq p_{0}(k)$, is
bounded polynomially by the input size.

######  Lemma 1.

There is an optimum solution $\mathbf{x}^{*}$ for which, for any
$k\in\mathcal{K}$, and $p\neq p_{0}(k)$, $x_{pkt}^{*}\leq p_{0}(k)\leq P$.

###### Proof.

Consider an arbitrary optimum schedule $\mathbf{x}^{*}$ and assume that some
$x_{pkt}^{*}$, with $k\in\mathcal{K}$ and $p\neq p_{0}(k)$, is larger than
$p_{0}(k)$. Then, we build a schedule $\mathbf{x}^{\prime}$ with
$H^{\prime}=\max_{t}\sum_{p,k}px_{pkt}^{\prime}$ at most $H^{*}$ and which
satisfy all demands. We fix $q=\lfloor\frac{x_{pkt}^{*}}{p_{0}(k)}\rfloor\geq
1$. Let $\mathbf{x}^{\prime}$ be the same schedule than $\mathbf{x}^{*}$ but
replace, at period $t$, a number $p_{0}(k)q$ of $p$-resources processing jobs
of type $k$ by a number $pq$ of $p_{0}(k)$-resources processing also jobs of
type $k$. Observe that this transformation does not modify the volume taken
for period $t$. Moreover, the production is only modified for jobs of type $k$
and, as we used a more efficient configuration in the new schedule, the
production of jobs of type $k$ at period $t$ cannot decrease. Formally,

$\sum_{p^{\prime}=1}^{P}c_{p^{\prime}k}x^{\prime}_{p^{\prime}k}=\sum_{p^{\prime}=1}^{P}c_{p^{\prime}k}x^{*}_{p^{\prime}k}+q\left(pc_{p_{0}(k),k}-p_{0}(k)c_{pk}\right)=\sum_{p^{\prime}=1}^{P}c_{p^{\prime}k}x^{*}_{p^{\prime}k}+R$

By Definition 4, we know that $c_{p_{0}(k),k}\geq p_{0}(k)\frac{c_{pk}}{p}$,
so $R\geq 0$. In summary, schedule $\mathbf{x}^{\prime}$ ensures at least the
same production than $\mathbf{x}^{*}$, uses the same volume per period (same
$H^{*}$). Therefore, it is also an optimum schedule and it satisfies
$x_{pkt}^{\prime}\leq p_{0}(k)$. ∎

From now on, any optimum solution $\mathbf{x}^{*}$ of Multi_Bot will be
supposed to be such as the one described by Lemma 1.

##  4 Structure and analysis of the approximation algorithm

In this section, we present the shape of our approximation algorithm. This
will consist in two steps: first solving a slightly different problem from
Multi_Bot with only one period, second use its solution to propose a global
schedule for the $T$ periods. We show how the approximation ratio
$\frac{4}{3}$ can be obtained for the general Multi_Bot when one-period
problems are solved exactly.

###  4.1 Presentation of the algorithm

Our idea to design approximations algorithms for the general Multi_Bot
follows. We call this general framework Bot-approx:

  * •

Step 1. Compute a polynomial-sized collection $\Pi$ of packings with
structural properties (see Theorem 1 for details),

  * •

Step 2. For each $\bm{\pi}\in\Pi$, create an IMS instance
$\mathcal{I}({\bm{\pi}})$ with $T$ boxes and items which are directly obtained
from the packing $\bm{\pi}$ (transformation $\bm{\pi}\rightarrow I(\bm{\pi})$
is described in Section 4.2),

  * •

Step 3. Find an approached solution for all IMS instances
$\mathcal{I}({\bm{\pi}})$ with lpt-first. Return the one which corresponds to
the best schedule.

Step 1 is very fuzzy for now, and we will introduce in Section 5 our method
for computing this collection of packings. Our objective is to produce a
collection $\Pi$ containing at least one packing $\bm{\pi}\in\Pi$ which is a
good candidate for achieving a satisfying schedule $\mathbf{x}$ when we put
its $p$-resources into the periods. Indeed, at least one packing
$\bm{\pi}\in\Pi$ will allow us to return after Steps 2 and 3 a schedule
$\mathbf{x}$ with $H\leq\frac{4}{3}H^{*}$. The properties of this collection
$\Pi$ are presented in Theorem 1. In particular, all packings of $\Pi$ will
satisfy the demands $d_{k}$ for each type of job $k$, _i.e._
$\sum_{p\in\mathcal{P}}c_{pk}x_{pk}\geq d_{k}$.

######  Theorem 1.

Given some Multi_Bot instance, we can produce in polynomial time
$O(KP^{3}T^{3}+KP^{7})$ a collection $\Pi$ of at most $3P$ packings such that:

  * •

each packing in $\Pi$ satisfy all demands,

  * •

it contains at least one packing $\bm{\pi}$ which satisfies
$\emph{vol}(\bm{\pi})\leq\emph{vol}(\bm{\pi}^{*})$,

  * •

if $H^{*}<3P$, it contains at least one packing $\bm{\pi}^{\prime}$ which
satisfies $\emph{vol}(\bm{\pi^{\prime}})\leq\emph{vol}(\bm{\pi}^{*})$,
$\max(\bm{\pi^{\prime}})\leq H^{*}$, and
$\emph{scale}_{H^{*}}(\bm{\pi}^{\prime})\leq T$.

###### Proof.

Section 5 is entirely dedicated to the proof of this result. Its conclusion is
given in Section 5.4. ∎

In the remainder of this algorithm, we apply Steps 2 and 3 for any packing in
$\Pi$. Eventually, as the size of the collection is at most $3P$, we will
obtain a set of at most $3P$ schedules. We will simply keep the one which
provides the minimum $H$.

Step 2 will be detailed in Section 4.2. For some packing $\bm{\pi}\in\Pi$, a
natural idea is, for each value $x_{pk}$, $p\in\mathcal{P}$,
$k\in\mathcal{K}$, to create $x_{pk}$ items of size $p$ and solve IMS with $T$
boxes. Said differently, we can construct an instance, with exactly
$\sum_{k}x_{pk}$ items of size $p$ for each $p\in\mathcal{P}$, which will be
equivalent to the packing $\bm{\pi}$. In this way, a solution of this IMS
instance with $T$ boxes correspond to a schedule for the initial Multi_Bot
instance.

Unfortunately, this transformation might not be achieved in polynomial time as
values $x_{pk}$, which depend on demands $d_{k}$, can be exponential in the
input size of Multi_Bot. In other words, we would create an IMS instance of
exponential size. Hence, we present a polynomial-time method which allows us
to handle this issue and produce a polynomial-sized IMS instance for
$\bm{\pi}$, denoted by $\mathcal{I}({\bm{\pi}})$.

Eventually, Step 3 consists in applying lpt-first on each IMS instance
$\mathcal{I}({\bm{\pi}})$ \- created at Step 2 - with $T$ boxes. The solutions
obtained thus correspond to schedules, as the $T$ boxes of IMS represent the
periods of Multi_Bot and each of these periods contains a set of performed
jobs (represented by the items), characterized by a configuration
$p\in\mathcal{P}$ ans some type of job $k\in\mathcal{K}$. Consequently, the
output of the whole process is a collection of $\left|\Pi\right|\leq 3P$
schedules $\mathbf{x}$. Naturally, we keep the schedule with the minimum $H$.
We will show that it offers a $\frac{4}{3}$-approximation for Multi_Bot (see
Theorems 3 and 4).

Based on the Theorems 1, 3 and 4 cited above and proved in the remainder of
the article, we present the main result of this paper.

######  Theorem 2 (Approximation ratio of Bot-approx).

Bot-approx is a $\frac{4}{3}$-approximation algorithm for _Multi_Bot_.

###### Proof.

Consider some instance of Multi_Bot. We distinguish two cases, depending on
the value of $H^{*}$.

If $H^{*}\geq 3P$, then we know that the collection $\Pi$ computed at Step 1
contains a packing $\bm{\pi}$ with a smaller volume than $\bm{\pi}^{*}$
(Theorem 1). According to Theorem 3, the schedule $\mathbf{x}$ produced with
Lpt-first by considering this initial packing $\bm{\pi}$ offers the guarantee
that $H\leq\frac{4}{3}H^{*}$.

If $H^{*}<3P$, then, again from Theorem 1, collection $\Pi$ contains a packing
$\bm{\pi}^{\prime}$ with a smaller volume than $\bm{\pi}^{*}$ such that
$\max(\bm{\pi}^{\prime})\leq H^{*}$ and
$\mbox{scale}_{H^{*}}(\bm{\pi}^{\prime})\leq T$. By Theorem 4, the schedule
$\mathbf{x^{\prime}}$ produced with Lpt-first by considering this initial
packing $\bm{\pi}^{\prime}$ gives also $H^{\prime}\leq\frac{4}{3}H^{*}$.

As Bot-approx returns the schedule minimizing $H$ among all initial packings
$\bm{\pi}\in\Pi$, we are sure to obtain a final solution which uses at most
$\frac{4}{3}H^{*}$ resources. ∎

From now on, in the next sections, our objective is to prove Theorem 1
(Section 5), but also Theorems 3 and 4 (Section 4.3) which are the keystones
for the proof of Theorem 2.

###  4.2 Transformation of a packing into polynomial IMS

We assume now that we are working with some given packing $\bm{\pi}$, which
belongs to the collection computed with Theorem 1 and is a good candidate to
obtain an approximate solution for the Multi_Bot instance. The objective is to
“schedule” this packing into $T$ periods. Packing $\bm{\pi}$ satisfies all
demands $d_{k}$ of the Multi_Bot instance. In order to assign efficiently each
performed job of $\bm{\pi}$ into the periods, we model it as an IMS instance
and then use Lpt-first to ensure the approximation factor. We focus in this
subsection on the transformation from packing $\bm{\pi}$ to an IMS instance
$I(\bm{\pi})$.

A natural way to achieve such equivalent transformation is simply, for each
pair $k\in\mathcal{K},p\in\mathcal{P}$, to create $x_{pk}$ items of size $p$.
In this way, we obtain an IMS instance with a volume (i.e. total size of the
items) equal to $\mbox{vol}(\bm{\pi})$. Each item of $I(\bm{\pi})$ thus
represents a performed job and its size gives us the number $p$ of resources
it involves. Furthermore, we keep in memory, for each item (equivalently for
each $p$-resource of packing $\bm{\pi}$), which type of jobs this $p$-resource
performs, even if it has no impact on the instance $I(\bm{\pi})$. Hence,
assigning these items to a period $t\in\mathcal{T}$ produces a solution of IMS
which completely corresponds to a schedule, since it is equivalent to
assigning $p$-resources performing jobs of type $k$ to period $t$, i.e.
proposing some vector $\left(x_{pkt}\right)_{p,k,t}$.

Unfortunately, this simple transformation $\bm{\pi}\rightarrow I(\bm{\pi})$
can produce an exponential-sized instance. As mentioned in the previous
subsection, the values $x_{pk}$ might be exponential in the input size of
Multi_Bot, as they depend on capacities and demands which are numerical
values. To avoid an IMS instance of exponential size, our idea consists in
forming “large” items which will represent a set of $p$-resources, instead of
a single one. In fact, we will distinguish two cases. When
$\mbox{vol}(\bm{\pi})$ is upper-bounded by some polynomial function of $P$ and
$T$ given below, we use the natural process of transforming each value
$x_{pk}$ into $x_{pk}$ items of size $p$. Otherwise, each item will correspond
to a set of $p$-resources and the polynomial size of the constructed IMS
instance will be guaranteed. The formal definition follows.

######  Definition 5.

We define $I$ as a polynomial-time algorithm which given some packing
$\bm{\pi}=(x_{pk})_{p,k}$, produces an IMS instance with the following rules:

  * •

If $\emph{vol}(\bm{\pi})\leq 3PT$, for each pair
$p\in\mathcal{P},k\in\mathcal{K}$, add $x_{pk}$ items of size $p$ into
instance $I(\bm{\pi})$.

  * •

Otherwise, if $\emph{vol}(\bm{\pi})>3PT$, items will represent a set of at
most $\frac{\emph{vol}(\bm{\pi})}{3T}$ performed jobs with the same
configuration $p$ and performing the same type $k$ of jobs. Analytically, for
each $p$, let $\alpha_{p}=\lfloor\frac{\emph{vol}(\bm{\pi})}{3pT}\rfloor$. For
each pair $p\in\mathcal{P},k\in\mathcal{K}$, add
$\lfloor\frac{x_{pk}}{\alpha_{p}}\rfloor$ items of size $p\alpha_{p}$, and 1
item of size $p(x_{pk}-\lfloor\frac{x_{pk}}{\alpha_{p}}\rfloor\alpha_{p})$

The first case, $\mbox{vol}(\bm{\pi})\leq 3PT$, corresponds to the natural
transformation described above, so we do not give more details on it. However,
the second one, $\mbox{vol}(\bm{\pi})>3PT$, needs extra explanations. Here, an
item represents a “block” of several $p$-resources performing jobs of types
$k$, in order to ensure that $I(\bm{\pi})$ has a polynomial size in the
encoding of the initial Multi_Bot instance. Each item is thus associated with
a configuration $p$ and a type of job $k$. Considering some pair $(p,k)$,
almost all items associated with it (except one) represent a number
$\alpha_{p}$ of $p$-resources, so their size is $p\alpha_{p}$. Their number is
given by the division of $x_{pk}$ (number of $p$-resources performing jobs of
type $k$ in packing $\bm{\pi}$) by the number $\alpha_{p}$ of $p$-resources
represented by each block. But, if $x_{pk}$ is not a multiple of $\alpha_{p}$,
an extra item should be added into $I(\bm{\pi})$ to represent the remaining
$p$-resources.

Observe that, in both cases, the total volume of the IMS instance
$I(\bm{\pi})$ is equal to the volume of packing $\bm{\pi}$ as we represented
all the performed jobs into $I(\bm{\pi})$. But the crucial property ensured by
transformation $I$ is certainly that the returned IMS instance has a size
polynomial in $P,K,T$.

######  Lemma 2.

Let $\bm{\pi}$ be some packing. The IMS instance $I(\bm{\pi})$:

  1. 1.

contains $O(PKT)$ items,

  2. 2.

satisfies $\emph{vol}(I(\bm{\pi}))=\emph{vol}(\bm{\pi})$

  3. 3.

if $\emph{vol}(\bm{\pi})>3PT$ and
$\emph{vol}(\bm{\pi})\leq\emph{vol}(\bm{\pi}^{*})$, does not contain items of
size greater than $\frac{H^{*}}{3}$.

###### Proof.

1\. If $\mbox{vol}(\bm{\pi})\leq 3PT$, then the number of items is exactly
$\sum_{p,k}x_{pk}$ which is smaller than $\sum_{p,k}p\cdot
x_{pk}=\mbox{vol}(\bm{\pi})\leq 3PT$. Else, we know that for each pair
$(p,k)$, there are at most $\frac{x_{pk}}{\alpha_{p}}+1$ items. Let
$\mu_{p}=\frac{\mbox{vol}(\bm{\pi})}{3pT}$. As $\mu_{p}>1$,
$\alpha_{p}=\lfloor\mu_{p}\rfloor\geq\frac{\mu_{p}}{2}$. Hence,

$\frac{x_{pk}}{\alpha_{p}}=\frac{x_{pk}}{\lfloor\mu_{p}\rfloor}\leq\frac{2x_{pk}}{\mu_{p}}=6T\frac{p\cdot
x_{pk}}{\mbox{vol}(\bm{\pi})}\leq 6T.$

Consequently, the total number of items in $I(\bm{\pi})$ is at most
$PK(6T+1)$.

2\. The volume of an IMS instance is the sum of the sizes over all its items.
If $\mbox{vol}(\bm{\pi})\leq 3PT$, then
$\mbox{vol}(I(\bm{\pi}))=\sum_{p,k}p\cdot x_{pk}=\mbox{vol}(\bm{\pi})$.
Otherwise,

$\mbox{vol}(I(\bm{\pi}))=\sum_{p,k}\left(p\alpha_{p}\lfloor\frac{x_{pk}}{\alpha_{p}}\rfloor+p(x_{pk}-\lfloor\frac{x_{pk}}{\alpha_{p}}\rfloor\alpha_{p})\right)=\sum_{p,k}p\cdot
x_{pk}=\mbox{vol}(\bm{\pi}).$

3\. If $\mbox{vol}(\bm{\pi})>3PT$, then
$p\alpha_{p}=p\lfloor\frac{\mbox{vol}(\bm{\pi})}{3pT}\rfloor\leq\frac{\mbox{vol}(\bm{\pi})}{3T}$:
as the volume of $\bm{\pi}$ is at most the one of $\bm{\pi}^{*}$ and
$H^{*}\geq\frac{\mbox{vol}(\bm{\pi}^{*})}{T}$, it gives
$p\alpha_{p}\leq\frac{H^{*}}{3}$. ∎

###  4.3 Approximation analysis

The objective of this subsection is to show that, given the IMS instances
$\mathcal{I}({\bm{\pi}})$ we created with Steps 1 and 2, Lpt-first algorithm
provides a $\frac{4}{3}$-approximation for Multi_Bot on at least one of these
instances. Indeed, as each $\mathcal{I}({\bm{\pi}})$ contains $T$ boxes, which
can be seen as the periods of Multi_Bot, any of its solution can be directely
converted into a schedule $(x_{pkt})_{p,k,t}$.

We begin with the proof of Theorem 3. Given some packing $\bm{\pi}$ with a
smaller volume than $\bm{\pi}^{*}$ and which satisfy all demands, Lpt-first
achieves a $\frac{4}{3}$-approximation ratio under the condition: $H^{*}\geq
3P$.

######  Theorem 3.

Consider some _Multi_Bot_ instance and a packing $\bm{\pi}$ which satisfies
all demands. Moreover, $\emph{vol}(\bm{\pi})\leq\emph{vol}(\bm{\pi}^{*})$. If
$H^{*}\geq 3P$, then the schedule $\mathbf{x}$ returned by solving
$\mathcal{I}({\bm{\pi}})$ with Lpt-first verifies $H\leq\frac{4}{3}H^{*}$.

###### Proof.

Let $N$ be the number of items in $I(\bm{\pi})$. We know that $N=O(PKT)$ from
Lemma 2. We proceed by induction on the number $z$ of items packed by Lpt-
first. We prove that, for any $0\leq z\leq N$, the number of resources present
in each period (or box) after packing the $z$ most large items is at most
$\frac{4}{3}H^{*}$.

The base case is trivial: when $z=0$, no item was packed, so the current $H$
is zero. Now, assume we already packed the $z$ first items and we want to pack
item $z+1$. According to Lemma 2,
$\mbox{vol}(I(\bm{\pi}))=\mbox{vol}(\bm{\pi})\leq\mbox{vol}(\bm{\pi}^{*})$,
therefore there is necessarily a period which contains less than $H^{*}$
resources, otherwise the total volume would overpass $TH^{*}$, a
contradiction. So, the least filled period contains at most $H^{*}$ resources.
Refering to the transformation $I$, see Definition 5, if
$\mbox{vol}(\bm{\pi})\leq 3PT$, each item represents a $p$-resource, so we
pack item $z+1$ of size at most $P\leq\frac{H^{*}}{3}$ into it. The volume of
this period after adding item $z+1$ is at most $\frac{4}{3}H^{*}$. If
$\mbox{vol}(\bm{\pi})>3PT$, we also pack some item of size at most
$p\alpha_{p}\leq\frac{H^{*}}{3}$ according to Lemma 2. Together with the
induction hypothesis, this observation shows us that all periods use at most
$\frac{4}{3}H^{*}$ resources after packing $z+1$ items:
$H\leq\frac{4}{3}H^{*}$. ∎

Now we fix the other side of the tradeoff, i.e. when $H^{*}<3P$.

######  Theorem 4.

Consider some Multi_Bot instance with $\lambda=H^{*}$ and a packing $\bm{\pi}$
which satisfy all demands. Moreover,
$\emph{vol}(\bm{\pi})\leq\emph{vol}(\bm{\pi}^{*})$,
$\max(\bm{\pi})\leq\lambda$ and $\emph{scale}_{\lambda}(\bm{\pi})\leq T$. If
$H^{*}<3P$, the schedule $\mathbf{x}$ returned by solving
$\mathcal{I}({\bm{\pi}})$ with Lpt-first verifies $H\leq\frac{4}{3}H^{*}$.

###### Proof.

As $H^{*}<3P$, $\mbox{vol}(\bm{\pi})\leq\mbox{vol}(\bm{\pi}^{*})\leq
TH^{*}<3PT$, hence the transformation $I$ simply consists, for each pair
$(p,k)$, in adding $x_{pk}$ items of size $p$. As a consequence, each item
represents exactly one $p$-resource of packing $\bm{\pi}$.

Lpt-first packs first the items of sizes $p>\frac{2H^{*}}{3}$. We look at the
packing after adding only these big items. As $\lambda=H^{*}$ and
$\mbox{scale}_{\lambda}(\bm{\pi})\leq T$, then there are at most $T$ big
items. Moreover, all big items ($p>\frac{2H^{*}}{3}$) do not overpass a size
$H^{*}$, as $\max(\bm{\pi})\leq\lambda$. So, at this moment, at most 1 item is
present in each period, their size is at most $H^{*}$ resources, and the
periods which are not filled with one big item are empty.

Second, Lpt-first packs the medium items of sizes $p>\frac{H^{*}}{3}$ which
are not big. The empty boxes are filled and, when none of them is empty
anymore, the remaining medium items are packed upon another medium item, as
their boxes are less filled than the ones with big items. There cannot be
three medium items into one period $t$ and only one medium item into another
period $t^{\prime}$ since the volume of two medium items is at least
$\frac{2H^{*}}{3}$ and is necessarily larger than for exactly one medium item.
Consequently, if there is a period with at least three medium items, then all
other periods containing medium items are made up of two of them at least.
However, having such a period with three medium items contradicts the scale
criterion as we would have $\mbox{scale}_{\lambda}(\bm{\pi})>T$. Consequently,
there cannot be more than two medium items per period, and the number of
resources present in the periods filled with medium items is at most
$\frac{4H^{*}}{3}$.

Figure 3: The result of Lpt-first after filling periods with big and medium
items first. Items of sizes 1 and 2 ($p\leq\frac{\lambda}{3}$) have still to
be treated.

Figure 3 illustrates an example of item assignment with Lpt-first after
considering big (drawn in red) and medium (in green) items only. We fix
$\lambda=7$, $T=6$, and items sizes $(7,6,5,4,4,4,4,3,2,1,1)$. The small
items, in blue, are not put inside the boxes yet.

The end of the proof consists in applying again the argument used in the proof
of Theorem 3. Now, all periods contain at most $\frac{4H^{*}}{3}$ resources:
the periods with one big item do not exceed $H^{*}$ and the periods with at
most two medium items do not exceed $\frac{4H^{*}}{3}$. The remaining items
have size at most $\frac{H^{*}}{3}$, and
$\mbox{vol}(\bm{\pi})\leq\mbox{vol}(\bm{\pi}^{*})$. So, at any step, the least
filled period will contain at most $H^{*}$ resources in order to satisfy the
volume condition: we can pack a small item into it without exceeding the bound
$\frac{4H^{*}}{3}$. ∎

##  5 Generation of packings with small volume

The objective of this section is to generate suitable packings for
approximating Multi_Bot. More precisely, we aim at fixing the process of Step
1 of our algorithm Bot-approx. As stated in Theorem 1, we want to produce in
polynomial-time a collection $\Pi$ of packing with certain requirements. This
section is dedicated to the proof of Theorem 1. The conclusion of this proof
is given in Section 5.4.

We focus on the specific formulation of Multi_Bot where $T=1$. The objective
of this problem is to determine the minimum number of resources needed to
process all jobs - at least $d_{k}$ jobs of type $k$ for all $k\in\mathcal{K}$
\- in one single period, without reconfiguration. We denote it by
Multi_Bot_1P. Its mathematical formulation can be obtained by simply replacing
$T=1$ into the one given in Problem 1. A solution is thus a packing
$(x_{pk})_{p,k}$ as the parameter $t$ does not intervene anymore here. The
goal is to minimize the total number of resources, i.e.
$\sum_{k\in\mathcal{K}}\sum_{p\in\mathcal{P}}p\cdot x_{pk}$, while all demands
are satisfied, i.e. $\sum_{p\in\mathcal{P}}c_{pk}\cdot x_{pk}\geq d_{k}$ for
any $k\in\mathcal{K}$.

Concretely, solving Multi_Bot_1P provides us with the optimal way to process
all jobs during only one session. From Section 2.1, we know that the input
size of Multi_Bot_1P is $O(KP(\log c_{\mbox{\scriptsize{max}}}+\log
d_{\mbox{\scriptsize{max}}}))$. We will see in the remainder that an optimal
packing for Multi_Bot_1P can be found in polynomial time.

###  5.1 Optimal packings with limited volume and scale

To deal with the requirements of Theorem 1, we define a problem which is more
general than Multi_Bot_1P. We call it Multi_Bot_1P[$\lambda$, $\tau$]: it
makes two extra parameters $\lambda,\tau\in\mathbb{N}$ intervene, see Problem
3.

We describe the non-trivial constraints presented in Problem 3. Constraint
(12) means that we must have a sufficient capacity to satisfy all demands
$d_{k}$. Constraint (13) means that the volume of the packing must be at most
$\lambda T$. Constraint (14) means that a performed job must contain no more
than $\lambda$ resources. Finally, constraint (15) implies that the
$\lambda$-scale of the resulting packing must be less than $\tau$. Without
constraint (13), the problem would always admit a solution, but its volume $H$
could be as large as possible. Here, we are only interested in solutions with
a volume bounded by some polynomial function.

Observe that if $\lambda\rightarrow+\infty$, constraints (13), (14) and (15)
disappear and the problem “tends to” Multi_Bot_1P, which always admit a
solution. In the remainder, we abuse notation and denote by $\lambda=\infty$
this case. Our idea consists in solving Multi_Bot_1P[$\lambda$, $\tau$] for
$\tau=T$ and all values $\lambda\in\left\\{1,2,3,\ldots,3P-1,\infty\right\\}$:
if we find a solution, it will be put into collection $\Pi$.

######  Problem 3 (Multi_Bot_1P[$\lambda$, $\tau$]).

Input:
$\displaystyle\mathcal{K}=\left\\{1,\ldots,K\right\\},\mathcal{P}=\left\\{1,\ldots,P\right\\}$
$\displaystyle\emph{Capacities}~{}(c_{pk})_{\begin{subarray}{c}p\in\mathcal{P}\\\
k\in\mathcal{K}\end{subarray}}$
$\displaystyle\emph{Demands}~{}(d_{k})_{k\in\mathcal{K}}$
$\displaystyle\mathbf{\lambda},\tau\in\mathbb{N},1\leq\lambda\leq 3P$
Objective: $\displaystyle\emph{find a
packing}~{}\bm{\pi}=(x_{pk})_{\begin{subarray}{c}p\in\mathcal{P}\\\
k\in\mathcal{K}\end{subarray}}~{}\emph{which}$
$\displaystyle\emph{minimizes}~{}H~{}\emph{{or} answer NO}$ subject to:
$\displaystyle\sum_{p\in\mathcal{P}}c_{pk}\cdot x_{pk}\geq d_{k}$
$\displaystyle\forall k\in\mathcal{K}$ (12)
$\displaystyle\sum_{k\in\mathcal{K}}\sum_{p\in\mathcal{P}}p\cdot
x_{pk}=H\leq\lambda\tau$ (13) $\displaystyle x_{pk}=0$ $\displaystyle\forall
k\in\mathcal{K},p>\lambda$ (14)
$\displaystyle\sum_{k\in\mathcal{K}}\sum_{p>\frac{2\lambda}{3}}x_{pk}+\frac{1}{2}\sum_{k\in\mathcal{K}}\sum_{\frac{\lambda}{3}<p\leq\frac{2\lambda}{3}}x_{pk}\leq\tau$
(15) $\displaystyle x_{pk},H\in\mathbb{N}\mbox{, }$ $\displaystyle\forall
k\in\mathcal{K},p\in\mathcal{P}$ (16)

Concretely, let $\bm{\pi}(\lambda)$ denote an optimum packing for
Multi_Bot_1P[$\lambda$, $T$] if it exists. We define:

$\Pi=\left\\{\bm{\pi}(\lambda):1\leq\lambda\leq
3P-1~{}\mbox{or}~{}\lambda=\infty\right\\}$ (17)

Collection $\Pi$ will contain at least 1 packing because $\bm{\pi}(\infty)$
necessarily exists, and at most $3P$ packings. We prove now that the optimum
solutions for all these problems produce the expected collection of packings.

######  Theorem 5.

Packings $\bm{\pi}(\lambda)$ satisfy the following properties:

  1. 1.

for any $\lambda$, $\bm{\pi}(\lambda)$, if it exists, reaches all demands
$d_{k}$,

  2. 2.

$\emph{vol}(\bm{\pi}(\infty))\leq\emph{vol}(\bm{\pi}^{*})$,

  3. 3.

if $H^{*}<3P$, then $\bm{\pi}(H^{*})$ exists and we have:
$\emph{vol}(\bm{\pi}(H^{*}))\leq\emph{vol}(\bm{\pi}^{*})$,
$\max(\bm{\pi}(H^{*}))\leq H^{*}$,
$\emph{scale}_{H^{*}}(\bm{\pi}(H^{*}))\leq~{}T$.

###### Proof.

1\. The constraint (12) implies that any solution achieves all demands,
independently from value $\lambda$.

2\. Observe that the solutions (not necessarily optimal) of
$\textbf{Multi\\_Bot\\_1P}[\infty,T]$ correspond exactly to the set of
packings satisfying all demands - constraint (12). Indeed, constraints (14)
and (15) disappear when $\lambda=\infty$. In particular, $\bm{\pi}^{*}$ is one
of these solutions and hence
$\mbox{vol}(\bm{\pi}(\infty))\leq\mbox{vol}(\bm{\pi}^{*})$.

3\. The reasoning is similar: if $H^{*}<3P$, then $\bm{\pi}^{*}$ is a solution
of
$\textbf{Multi\\_Bot\\_1P}[H^{*},T]$. Obviously it satisfies all demands and
its volume is at most $TH^{*}$. Furthermore, as each period in schedule
$\mathbf{x^{*}}$ contains at most $H^{*}$ resources, i.e.
$H_{t}^{*}=\sum_{p,k}x_{pkt}^{*}\leq H^{*}$, then necessarily $x_{pkt}=0$ when
$p>H^{*}$. So, $x_{pk}=0$ for $p>H^{*}$ and any $k\in\mathcal{K}$. Finally,
each period of schedule $\mathbf{x}^{*}$ cannot contain both a big
configuration ($p>\frac{2H^{*}}{3}$) and a medium one
($\frac{H^{*}}{3}<p\leq\frac{2H^{*}}{3}$). It cannot contain either three
medium ones as it overpasses capacity $H^{*}$. As a conclusion, each period
contains at most either a big configuration or two medium ones: the
$H^{*}$-scale of $\bm{\pi}^{*}$ is at most $T$. Hence,
$\textbf{Multi\\_Bot\\_1P}[H^{*},T]$ admits at least one solution
$\bm{\pi}^{*}$, so $\bm{\pi}(H^{*})$ exists. As $\bm{\pi}(H^{*})$ is the
solution minimizing the volume, we have
$\mbox{vol}(\bm{\pi}(H^{*}))\leq\mbox{vol}(\bm{\pi}^{*})$. The two other
inequalities are the consequences of the definition of
$\textbf{Multi\\_Bot\\_1P}[H^{*},T]$. ∎

The collection $\Pi$ meets the requirements of Theorem 1. Now, we prove that
all these packings can be built in polynomial time.

###  5.2 Dynamic programming for the single-period problems

We begin with the generation of packings $\bm{\pi}(\lambda)$ for
$1\leq\lambda\leq 3P-1$. We will fix the case $\lambda=\infty$ in Section 5.3.
We fix some positive integer $\lambda$ with $\lambda\leq 3P-1$. Our objective
is to solve $\textbf{Multi\\_Bot\\_1P}[\lambda,T]$ and, hence, to obtain
either some packing $\bm{\pi}(\lambda)$ or a negative answer. We present a
dynamic programming (DP) procedure to achieve this task.

Structure of DP memory. From now on, variable $\tau$ represents a positive
half-integer upper-bounded by $T$ and $W$ a positive integer representing the
authorized volume, which is at most $\lambda T$.

We construct a four-dimension vector Table, whose elements are
$\texttt{Table}[p,k,W,\tau]$ with three integers $0\leq p\leq\lambda$, $1\leq
k\leq K$, $0\leq W\leq\lambda T$ and a half-integer $0\leq\tau\leq T$. Hence,
the total size of the vector is $\lambda^{2}T^{2}K=O(P^{2}T^{2}K)$. The role
of this vector is to help us producing intermediary packings which allows us
to obtain potentially the solution of $\textbf{Multi\\_Bot\\_1P}[\lambda,T]$.
We denote by $\bm{\pi}[p,k,W,\tau]$ a packing which:

  * •

produces only jobs of type $1,2,\ldots,k$: $x_{pk^{\prime}}=0$ when
$k^{\prime}>k$,

  * •

uses only configurations $1,2,\ldots,p$ to process the jobs of type $k$:
$x_{p^{\prime}k}=0$ when $p^{\prime}>p$,

  * •

satisfies the demands until $d_{k-1}$:
$\sum\limits_{p^{\prime}=1}^{\lambda}c_{p^{\prime}k^{\prime}}\cdot
x_{p^{\prime}k^{\prime}}\geq d_{k^{\prime}}$ for all $1\leq k^{\prime}<k$,

  * •

has a volume at most $W$:
$\sum\limits_{p^{\prime}=1}^{\lambda}\sum\limits_{k^{\prime}=1}^{k}p^{\prime}\cdot
x_{p^{\prime}k^{\prime}}\leq W$,

  * •

has a $\lambda$-scale at most $\tau$:
$\mbox{scale}_{\lambda}(\bm{\pi})\leq\tau$,

  * •

maximizes the number of jobs of type $k$ processed, i.e.
$\sum\limits_{p^{\prime}=1}^{\lambda}c_{p^{\prime}k}\cdot x_{p^{\prime}k}$.

Packing $\bm{\pi}[p,k,W,\tau]$ does not necessarily exist since reaching the
demands might be avoided by the volume and scale conditions. Observe that, by
definition, $\textbf{Multi\\_Bot\\_1P}[\lambda,T]$ admits a solution if and
only if $\bm{\pi}[\lambda,K,\lambda T,T]$ exists and satisfies the demands for
jobs of type $K$. Also, for the specific value $p=0$, the packing
$\bm{\pi}[0,k,W,\tau]$ cannot use any configuration for jobs of type $k$, so
in fact it does not process jobs of type $k$ at all. We can fix:
$\bm{\pi}[0,k,W,\tau]=\bm{\pi}[\lambda,k-1,W,\tau]$. The particular case $p=0$
and $k=1$ gives an empty packing $\bm{\pi}[0,1,W,\tau]$: it will be forgotten
in the remainder.

The objective of vector Table is to contain either the production of jobs of
type $k$ by $\bm{\pi}[p,k,W,\tau]$ if it exists, or $-\infty$. More formally,

$\texttt{Table}[p,k,W,\tau]=\left\\{\begin{split}&\sum_{p^{\prime}=1}^{p}c_{p^{\prime}k}x_{p^{\prime}k}&\mbox{if}~{}\bm{\pi}[p,k,W,\tau]=(x_{p^{\prime}k^{\prime}})_{p^{\prime},k^{\prime}}~{}\mbox{exists}\\\
&-\infty&\mbox{otherwise}\\\ \end{split}\right.$ (18)

In addition, we also compute two vectors Bool and Pack with the same dimension
sizes than Table. Vector Bool simply indicates, with a boolean, whether
$\bm{\pi}[p,k,W,\tau]$ satisfies the demand $d_{k}$ for jobs of type $k$
($\texttt{Bool}[p,k,W,\tau]=\mbox{True}$) or not ($=\mbox{False}$). Finally,
vector Pack provides us with some information which allows us to retrieve
exactly the composition of $\bm{\pi}[p,k,W,\tau]$. More details on vector Pack
will follow.

Before stating our recursive formula to achieve the DP algorithm, we define an
extra function $S_{p,\lambda}$ for any $1\leq p\leq\lambda$. Given some half-
integer “budget” $\tau$ and an integer $j$, it returns the updated
$\lambda$-scale budget which remains after adding a number $j$ of
$p$-resources to some packing. Formally,

$S_{p,\lambda}(\tau,j)=\left\\{\begin{split}&\tau&\mbox{if}~{}p\leq\frac{\lambda}{3}\\\
&\tau-\frac{j}{2}&\mbox{if}~{}\frac{\lambda}{3}<p\leq\frac{2\lambda}{3}\\\
&\tau-j&\mbox{if}~{}p>\frac{2\lambda}{3}\\\ \end{split}\right.$

Recursive formula. We state now a recursive formula for computing all values
of Table, Bool and Pack. We begin with the recursive scheme of Table and Bool.

The base case is $p=k=1$. Packing $\bm{\pi}[1,1,W,\tau]$ has no demand to
satisfy, therefore it necessarily exists. It corresponds to taking the maximum
number of $1$-resources which satisfy both the volume and scale conditions:

$\forall
W,\forall\tau,~{}~{}~{}\texttt{Table}[1,1,W,\tau]=\max_{\begin{subarray}{c}0\leq
j\leq W\\\ S_{1,\lambda}(\tau,j)\geq 0\end{subarray}}j\cdot c_{11}$ (19)
$\texttt{Bool}[1,1,W,\tau]=\mbox{True}\Leftrightarrow\texttt{Table}[1,1,W,\tau]\geq
d_{1}$ (20)

For the general statement, we distinguish two cases. First assume that $p=0$
and $k>1$. We have $\bm{\pi}[0,k,W,\tau]=\bm{\pi}[\lambda,k-1,W,\tau]$.

$\texttt{Table}[0,k,W,\tau]=\left\\{\begin{split}&0&\mbox{if}~{}\texttt{Table}[\lambda,k-1,W,\tau]\geq
d_{k-1}\\\ &-\infty&\mbox{otherwise}\\\ \end{split}\right.$ (21)
$\texttt{Bool}[0,k,W,\tau]=\mbox{False}$ (22)

Second, assume that $p\geq 1$, i.e. jobs of type $k$ can be processed by
$p^{\prime}$-resources, with $p^{\prime}\leq p$. We write:

$\texttt{Table}[p,k,W,\tau]=\max_{\begin{subarray}{c}0\leq
j\leq\lfloor\frac{W}{p}\rfloor\\\ S_{p,\lambda}(\tau,j)\geq 0\\\
\texttt{Bool}[\lambda,k-1,W-jp,S_{p,\lambda}(\tau,j)]\end{subarray}}\texttt{Table}[p-1,k,W-jp,S_{p,\lambda}(\tau,j)]+jc_{pk}$
(23)
$\texttt{Bool}[p,k,W,\tau]=\mbox{True}\Leftrightarrow\texttt{Table}[p,k,W,\tau]\geq
d_{k}$ (24)

Index $j$ represents the number of $p$-resources we might add to our packing.
Naturally, this addition should overpass neither the volume constraint
($j\leq\frac{W}{p}$), nor the scale one ($S_{p,\lambda}(\tau,j)\geq 0$).
Furthermore, $\texttt{Bool}[\lambda,k-1,W-jp,S_{p,\lambda}(\tau,j)]$ must be
True as it guarantees that demands $d_{1},\ldots,d_{k-1}$ can be satisfied
before the add-on of $j$ $p$-resources. It may happen that no index $j$ (even
$j=0$) satisfies these three conditions. In this case, we fix
$\texttt{Table}[p,k,W,\tau]=-\infty$.

Observe that $\texttt{Table}[p,k,W,\tau]=-\infty$ if and only if
$\texttt{Bool}[\lambda,k-1,W,\tau]$ is False. This makes sense since it means
that with the volume $W$ and the scale $\tau$ we are considering, the demands
for jobs of type $1,2,\ldots,k-1$ could not be reached. Figure 4 provides us
with a 2D-view of vector Table, highlighting the area where values are base
cases and giving examples of recursive calls, following Equations (21) and
(23). We prove that $\texttt{Table}[p,k,W,\tau]$ is equal to the expectations
expressed in Equation (18).

Figure 4: 2D-projection of the 4D-vector Table illustrating the different
recursive calls

######  Lemma 3.

If $\bm{\pi}[p,k,W,\tau]=(x_{p^{\prime}k^{\prime}})_{p^{\prime},k^{\prime}}$
exists, then:

  * •

$\emph{{Table}}[p,k,W,\tau]=\sum_{p^{\prime}}c_{p^{\prime}k}x_{p^{\prime}k}$.

  * •

$\emph{{Bool}}[p,k,W,\tau]=\emph{True}$ if and only if $\bm{\pi}[p,k,W,\tau]$
satisfies demand $d_{k}$.

Otherwise, $\emph{{Table}}[p,k,W,\tau]=-\infty$ and
$\emph{{Bool}}[p,k,W,\tau]=\emph{False}$.

###### Proof.

First, we handle the base case. If $p=k=1$, then $\bm{\pi}[1,1,W,\tau]$ exists
and is the singleton packing $(x_{11})$ which processes the maximum number of
jobs of type $1$ with $1$-resources while satisfying both the volume and scale
constraints. Then, $\texttt{Table}[1,1,W,\tau]$ must be equal to
$x_{11}c_{11}$, which perfectly fits with the definition given in Equation
(19). Moreover, according to Equation (20), $\texttt{Bool}[1,1,W,\tau]$ is
True if and only if $\bm{\pi}[1,1,W,\tau]$ reaches demand $d_{k}=d_{1}$.

We proceed inductively. Assume that the statement is achieved not only for all
pairs $(p^{\prime},k^{\prime})$ such that $k^{\prime}<k$ but also when
$k^{\prime}=k^{\prime}$ and $p^{\prime}<p$.

If $\bm{\pi}[p,k,W,\tau]$ does not exist, then it means that demands
$d_{1},\ldots,d_{k-1}$ cannot be satisfied with volume $W$ and scale $\tau$
constraints. So, $\texttt{Table}[\lambda,k-1,W,\tau]<d_{k-1}$ and
$\texttt{Bool}[\lambda,k-1,W,\tau]$ is False by induction. Consequently,
Equations (21) and (23) ensure us that $\texttt{Table}[p,k,W,\tau]=-\infty$
and $\texttt{Bool}[p,k,W,\tau]=\mbox{False}$, as expected. In the remainder of
this proof, we assume $\bm{\pi}[p,k,W,\tau]$ exists.

If $p=0$, then $\bm{\pi}[0,k,W,\tau]=\bm{\pi}[\lambda,k-1,W,\tau]$. As this
packing does not process any job of type $k$, we fixed
$\texttt{Table}[p,k,W,\tau]=0$, see Equation (21). Hence, as stated in
Equation (22), $\bm{\pi}[0,k,W,\tau]$ obviously does not satisfy demand
$d_{k}>0$.

If $p>0$, then $\bm{\pi}[p,k,W,\tau]$ is made up of a certain number $j\geq 0$
of $p$-resources which process jobs of type $k$, and all other components
which can be seen together as a slightly smaller packing. The latter packing
must satisfy the demands for jobs of type $1,\ldots,k-1$ and also maximize the
number of processed jobs of type $k$ with configurations $1,\ldots,p-1$, while
fulfilling the volume and scale constraints, even if we know that already a
number $j$ of $p$-resources have to be counted. Hence, $\bm{\pi}[p,k,W,\tau]$
can be obtained from $\bm{\pi}[p-1,k,W-jp,S_{p,\lambda}(\tau,j)]$ by adding
only $x_{pk}=j$. This justifies Equation (23). Finally, as stated in Equation
(24), $\texttt{Bool}[p,k,W,\tau]$ is True if and only if demand $d_{k}$ is
satisfied by $\bm{\pi}[p,k,W,\tau]$, i.e. $\texttt{Table}[p,k,W,\tau]\geq
d_{k}$. ∎

Values $\texttt{Table}[p,k,W,\tau]$ provide us with the number of jobs of type
$k$ processed by optimum packings $\bm{\pi}[p,k,W,\tau]$. Nevertheless, our
initial objective is to obtain the composition of these packings. To achieve
it, we create a third table Pack with the same dimensions than Table and Bool.
A first natural idea would be to fill each element $\texttt{Pack}[p,k,W,\tau]$
with the packing $\bm{\pi}[p,k,W,\tau]$. However, as the encoding size of
$\bm{\pi}[p,k,W,\tau]$ is at least $PK$, it will have some relatively strong
impact on the complexity of our algorithm. Hence, we fill
$\texttt{Pack}[p,k,W,\tau]$ only with the necessary information needed to
retrieve the packings.

If $\texttt{Table}[p,k,W,\tau]=-\infty$ or $p=0$, then
$\texttt{Pack}[p,k,W,\tau]$ is kept empty. Else, we define
$\texttt{Pack}[p,k,W,\tau]$ as the integer $j$ which is the number of
$p$-resources processing jobs of type $k$ in $\bm{\pi}[p,k,W,\tau]$.

$\texttt{Pack}[p,k,W,\tau]=\left\\{\begin{split}&j~{}\mbox{if}~{}p=k=1~{}\mbox{and}~{}\texttt{Table}[1,1,W,\tau]=jc_{11}\\\
&j~{}\mbox{if}~{}\texttt{Table}[p,k,W,\tau]=\texttt{Table}[p-1,k,W-jp,S_{p,\lambda}(\tau,j)]+jc_{pk}\\\
&\mbox{empty otherwise}\end{split}\right.$ (25)

Observe that the encoding size of each value $\texttt{Pack}[p,k,W,\tau]$ is
now $O(\log(\lambda T))$. Some packing $\bm{\pi}[p,k,W,\tau]$ can now be
recovered with the following process, we call Recover:

  * •

if $\texttt{Table}[p,k,W,\tau]=-\infty$, then $\bm{\pi}[p,k,W,\tau]$ does not
exist.

  * •

if $p=k=1$ and $\texttt{Pack}[1,1,W,\tau]=j$, then $\bm{\pi}[1,1,W,\tau]$ is
the singleton $(x_{11})$ with $x_{11}=j$.

  * •

if $p=0$ and $k>1$, then $\bm{\pi}[0,k,W,\tau]=\bm{\pi}[\lambda,k-1,W,\tau]$.

  * •

if $\texttt{Pack}[p,k,W,\tau]=j$, compute recursively packing
$\bm{\pi}[p-1,k,W-jp,S_{p,\lambda}(\tau,j)]$ with Recover and add $x_{pk}=j$
to it.

1 Input: Instance of $\textbf{Multi\\_Bot\\_1P}[\lambda,T]$

2 Output: A packing $\bm{\pi}(\lambda)$ or answer NO

3 Initialize Table, Bool and Pack as empty vectors;

4 for  _all $1\leq W\leq\lambda T$ and $1\leq\tau\leq T$_ do

5 fix $\texttt{Table}[1,1,W,\tau]$, $\texttt{Bool}[1,1,W,\tau]$,
$\texttt{Pack}[1,1,W,\tau]$ with respectively Equations (19), (20), and (25);

6 endfor

7$p=1$;

8 for  _all $1\leq k\leq K$_ do

9 while  _$p\leq\lambda$_ do

10 for  _all $1\leq W\leq\lambda T$ and $1\leq\tau\leq T$_ do

11 fix $\texttt{Table}[p,k,W,\tau]$, $\texttt{Bool}[p,k,W,\tau]$,
$\texttt{Pack}[p,k,W,\tau]$ with Equations (21-25);

12 endfor

13$p=p+1$

end while

14$p=0$;

15 endfor

16$D=\texttt{Table}[\lambda,K,\lambda T,T]$;

17 if  _$D\geq d_{K}$_ then return Recover$(\lambda,K,\lambda T,T)$

18 return NO

Algorithm 1 Exact algorithm Bot-ProgDyn which solves
$\textbf{Multi\\_Bot\\_1P}[\lambda,T]$

We remind that if $\texttt{Table}[\lambda,K,\lambda T,T]\geq 0$, then
$\bm{\pi}[\lambda,K,\lambda T,T]$ exists and it gives us some
$\bm{\pi}(\lambda)$ if and only if the demand $d_{K}$ is achieved. Otherwise,
if $\texttt{Table}[\lambda,K,\lambda T,T]=-\infty$, then there is no packing
$\bm{\pi}(\lambda)$ for sure. As a consequence, the following algorithm solves
$\textbf{Multi\\_Bot\\_1P}[\lambda,T]$: first compute simultaneously the three
tables Table, Bool and Pack, second answer NO if
$\texttt{Table}[\lambda,K,\lambda T,T]=-\infty$, otherwise retrieve packing
$\bm{\pi}[\lambda,K,\lambda T,T]$ recursively with sub-routine Recover. If
$\bm{\pi}[\lambda,K,\lambda T,T]$ satisfies demand $d_{K}$, then return it as
$\bm{\pi}(\lambda)$, else answer NO. We call this algorithm Bot-ProgDyn
(Algorithm 1).

######  Theorem 6.

Bot-ProgDyn solves $\textbf{Multi\\_Bot\\_1P}[\lambda,T]$ with a running time
$O(\lambda^{3}T^{3}K)$.

###### Proof.

From Lemma 3, we know that $\texttt{Table}[\lambda,K,\lambda T,T]\geq d_{K}$
if and only if $\bm{\pi}(\lambda)$ exists. Therefore, as Bot-ProgDyn achieves
the dynamic programming to fills Table, it returns the solution of
$\textbf{Multi\\_Bot\\_1P}[\lambda,T]$.

We focus now on the running time of Bot-ProgDyn. The dyanmic programming
routine uses a memory space of size $O(\lambda^{2}T^{2}K)$, and each
computation uses at most $\lambda T$ recursive calls: the worst case occurs
with Equation (23) and the computation of $\texttt{Table}[\lambda,K,\lambda
T,T]$. Consequently, the number of comparisons/affectations/arithmetic
operations is $O(\lambda^{3}T^{3}K)$.

Furthermore, the time needed to apply recover is negligible compared to the
latter. Indeed, the number of recursive calls needed to compute
$\bm{\pi}(\lambda,K,\lambda T,T)$ is at most the size of vector Pack, which is
$O(\lambda^{2}T^{2}K)$. ∎

###  5.3 Optimum packing with unlimited scale

We focus on problem Multi_Bot_1P, which is equivalent to
$\textbf{Multi\\_Bot\\_1P}[\infty,T]$ ($T$ has no influence here). In other
words, we aim at producing the packing $\bm{\pi}(\infty)$ which will be
denoted $\bm{\pi}$ in this subsection to simplify notations.

Our reasoning is based on the result stated in Lemma 1. We will assume that
the packing $\bm{\pi}=(x_{pk})_{p,k}$ admits low values for non-optimum
configurations, i.e. $x_{pk}\leq p_{0}(k)$ for any $k\in\mathcal{K}$ and
$p\neq p_{0}(k)$ (consequence of Lemma 1). This packing $\bm{\pi}$ can be
decomposed into two parts: on one hand, the values $x_{p_{0}(k),k}$ for
optimal configurations and, on the other hand, a packing
$\bm{\pi}^{\prime}=(x_{pk}^{\prime})_{p,k}$ taking only values for non-optimum
configurations. Formally,

$x_{pk}^{\prime}=\left\\{\begin{split}&x_{pk}&\mbox{if}~{}k\in\mathcal{K},p\in\mathcal{P},p\neq
p_{0}(k)\\\ &0&\mbox{if}~{}k\in\mathcal{K},p=p_{0}(k)\\\ \end{split}\right.$

This sub-packing, as expected, has a small volume. Let
$W(P)=P\frac{P(P-1)}{2}$. We have
$\mbox{vol}(\bm{\pi}^{\prime})=\sum_{p,k}p\cdot
x_{pk}^{\prime}\leq\sum_{k}\sum_{p\neq p_{0}(k)}p\cdot p_{0}(k)\leq K\cdot
W(P).$ More precisely, the volume of $\bm{\pi}^{\prime}$ dedicated to each
type of job is at most $W(P)$.

Our construction of packing $\bm{\pi}$ is inductive. For any $1\leq k\leq K$,
we denote by $\bm{\pi}_{j}=(x_{pk}^{(j)})_{p,k}$ a packing satisfying the
following properties:

  * •

$\bm{\pi}_{j}$ satisfies the demands for all types of jobs,

  * •

for any $1\leq i\leq j$, $\bm{\pi}_{j}$ uses the minimum number of resources
to satisfy demand $d_{i}$ with all configurations allowed,

  * •

for any $j<i\leq K$, uses the minimum number of resources to satisfy demand
$d_{i}$ with only configuration $p_{0}(j)$ allowed.

First, observe that $\bm{\pi}_{K}$ is a solution of Multi_Bot_1P since it
satisfies all demands while minimizing the total volume of the packing.
Therefore, we can state $\bm{\pi}=\bm{\pi}_{K}$. Furthermore, $\bm{\pi}_{0}$
is a packing satisfying all demands which minimizes the total volume by using
only optimal configurations for each type of jobs. It can be determined
analytically and this will be the base case of our induction. For any $1\leq
k\leq K$,

$x_{p_{0}(k),k}=\left\lceil\frac{d_{k}}{c_{p_{0}(k),k}}\right\rceil$

By definition, all other components of packing $\bm{\pi}_{0}$ are zero. Below,
we proceed the inductive step.

######  Lemma 4.

Assume packing $\bm{\pi}_{j}$ is known. One can build packing $\bm{\pi}_{j+1}$
in time $O(W(P)^{2}P)$ using the algorithm Bot-ProgDyn.

###### Proof.

We remind that we are working on some instance $\mathcal{I}$ of
$\textbf{Multi\\_Bot\\_1P}=\textbf{Multi\\_Bot\\_1P}[\infty,0]$ (we remind
that when $\lambda=\infty$, then the second parameter has no influence on the
definition of the problem, so we put 0 arbitrarily). We define another
instance $\mathcal{J}$ of $\textbf{Multi\\_Bot\\_1P}[\infty,0]$. Instance
$\mathcal{J}$ contains only one job type, which corresponds to the jobs of
type $j+1$ in $\mathcal{I}$. Then, the capacities in $\mathcal{J}$ are exactly
the capacities $c_{p(j+1)}$ of jobs of type $j+1$ in $\mathcal{I}$, except for
the optimal configuration for which we fix $c_{p_{0}(j+1),j+1}=0$. Concretely,
$p_{0}(j+1)$ will not be used in the solutions of $\mathcal{J}$. We do not
need to fix any demand constraint because, with only one job type, it will not
intervene in algorithm Bot-ProgDyn.

Using Bot-ProgDyn on instance $\mathcal{J}$, we build vectors Table and Pack
(with exactly one job type, Bool is not necessary) with limited volume $W(P)$.
In brief, we stop the procedure when $\texttt{Table}[P,1,W(P),0]$ and
$\texttt{Pack}[P,1,W(P),0]$ are obtained. Thanks to these vectors, we are able
to obtain, for any volume $0\leq W\leq W(P)$, a packing which processes only
jobs of type $j+1$, with volume at most $W$, and which maximizes the
production.

By induction hypothesis, we know that packing $\bm{\pi}_{j}$ already minimizes
the volume used to process the necessary demand for jobs of type $1,\ldots,j$.
Thus, we focus only on jobs of type $j+1$. Moreover, the volume $W$ used to
process jobs of type $j+1$ in packing $\bm{\pi}_{j+1}$ with non-optimal
configurations does not exceed $W(P)$ (consequence of Lemma 1). Hence, we
compute for all possible volumes $0\leq W\leq W(P)$, the packing which
maximizes the production of jobs of type $j+1$ while maintaining at most
volume $W$. The production of such packing is given by
$\texttt{Table}[P,1,W,0]$. It suffices to guess the volume $W$ taken by non-
optimal configurations, to compute the packing maximizing the production of
jobs of type $j+1$ with this volume and, eventually, to add optimal
configurations $p_{0}(j+1)$ while the demand is not satisfied. At least one of
these volumes $W$ will provide us with a packing $\bm{\pi}_{j+1}$ satisfying
the properties stated above. Formally, we define:

$W_{j+1}=\min_{0\leq W\leq
W(P)}W+\left\lceil\frac{d_{j+1}-\texttt{Table}[P,1,W,0]}{c_{p_{0}(j+1),(j+1)}}\right\rceil.$
(26)

The right-hand side of Equation (26) is the total volume used for processing
jobs of type $j+1$ when the demand has to be satisfied and also when exactly
$W$ resources are assigned to non-optimum configurations.

Once the optimum volume $W_{j+1}$ for non-optimum configurations was
determined, we fix, for the optimal configuration $p_{0}(j+1)$:

$x_{p_{0}(j+1),j+1}^{(j+1)}=\left\lceil\frac{d_{j+1}-\texttt{Table}[P,1,W_{j+1},0]}{c_{p_{0}(j+1),(j+1)}}\right\rceil$

For $p\neq p_{0}(j+1)$, the number of $p$-resources assigned for the process
of jobs of type $j+1$ is directly given by the packing which can be recovered
from $\texttt{Pack}[P,1,W_{j+1},0]$. ∎

######  Theorem 7.

Multi_Bot_1P can be solved in time $O(KP^{7})$.

###### Proof.

We state the full inductive process here. First, we compute packing
$\bm{\pi}_{0}$ with analytical formulas in time $O(KP)$. Then, we construct
inductively all packings $\bm{\pi}_{j}$ for $1\leq j\leq K$ thanks to Lemma 4.
Eventually, packing $\bm{\pi}_{K}$ provides us with a solution of
Multi_Bot_1P. As there are exactly $K$ inductive steps and each step runs in
$O(P^{7})$ according to Theorem 6, the total running time for computing
$\bm{\pi}(\infty)$ is $O(KP^{7})$. ∎

###  5.4 Computation of collection $\Pi$

Combining the results obtained in both Sections 5.2 and 5.3, we are now ready
for the computation of the whole collection $\Pi$ of packings which will allow
us to obtain a $\frac{4}{3}$-approximation for Multi_Bot.

Proof of Theorem 1. According to Theorem 6, each packing $\bm{\pi}(\lambda)$,
$1\leq\lambda\leq 3P-1$, can be produced in time $O(\lambda^{3}T^{3}K)$ (or
the algorithm warns us that such packing does not exist). Then, according to
Theorem 7, packing $\bm{\pi}(\infty)$ can be computed in time $O(KP^{7})$.
Consequently, we build the collection described in Equation (17) with the time
announced.

By definition, any packing $\bm{\pi}(\lambda)$, if it exists, satisfies all
demands (Problem 3). Packing $\bm{\pi}(\infty)$, which necessarily exists, is
the packing which satisfies all demands while minimizing the volume. As
$\bm{\pi}^{*}$ is a (not necessarily optimal) solution of Multi_Bot_1P, then
its volume is at least $\mbox{vol}(\bm{\pi}(\infty))$. Finally, if $H^{*}<3P$,
then packing $\bm{\pi}(H^{*})$ exists since $\bm{\pi}^{*}$ is a solution of
$\textbf{Multi\\_Bot\\_1P}[H^{*},T]$: it satisfies all demands, its volume is
at most $TH^{*}$, its maximum at most $H^{*}$ and its scale is at most $T$. ∎

##  6 Conclusion and perspectives

In this article, we present a $\frac{4}{3}$-approximation for a combinatorial
problem - generalizing high-multiplicity IMS \- which consists in finding the
optimum schedule for a fleet of reconfigurable robots given some demands for
all types of processed jobs. We believe that this problem, we called
Multi_Bot, could describe many situations involving reconfigurable systems,
such as work plannings for teams of employees for example. Therefore, our
approximation algorithm is, in our opinion, not only an important achievement
for the industrial use of reconfigurable robots but also for other scheduling
areas. Indeed, it offers the theoretical guarantee to be close to the optimum
schedule, and in practice the performance should be in fact much smaller than
this upper bound.

A drawback of our algorithm could be the exponent 7 over parameter $P$ in its
running time. For the reconfigurable robots application, it is not since in
practice $P$ is smaller than $15$ (no more than 14 elementary robots of
MecaBotiX can be assembled together). Nevertheless, this time complexity has
to be taken into account and perhaps some improvements could be proposed.

A natural question is whether this approximation factor $\frac{4}{3}$ can be
improved. The answer is yes, as we are currently writing a PTAS for Multi_Bot.
This is a very interesting theoretical result, as it shows us that any
approximation factor can be achieved, but, at the same time, it does not offer
a performing running time for industrial application. This contribution will
be presented soon.

A possibility would be to design the same algorithm by replacing Lpt-first
with another heuristic for IMS, for example Multifit. Indeed, the
approximation ratio of Multifit is $\frac{13}{11}$. However, the analysis of
Multifit is much more involved [18] than the one for Lpt-first. As a
consequence, it is more difficult to see which are the properties our packings
should satisfy in order to obtain a lower approximation ratio for Multi_Bot.
Nevertheless, it will be the next direction of research to look at on this
subject.

## References

  * [1] O. Battaïa, X. Delorme, A. Dolgui, J. Hagemann, A. Horlemann, S. Kovalev, and S. Malyutin.  Workforce minimization for a mixed-model assembly line in the automotive industry.  International Journal of Production Economics, 170:489–500, 2015\.
  * [2] U. Beşikci, U. Bilge, and G. Ulusoy.  Multi-mode resource constrained multi-project scheduling and resource portfolio problem.  European Journal of Operational Research, 240(1):22–31, 2015.
  * [3] N. Boysen, P. Schulze, and A. Scholl.  Assembly line balancing: What happened in the last fifteen years?  European Journal of Operational Research, 301(3):797–814, 2022\.
  * [4] N. Brauner, Y. Crama, A. Grigoriev, and J. van de Klundert.  A framework for the complexity of high-multiplicity scheduling problems.  J. Comb. Optim., 9(3):313–323, 2005.
  * [5] H. Brinkop and K. Jansen.  High multiplicity scheduling on uniform machines in FPT-time.  CoRR, abs/2203.01741, 2022.
  * [6] M. Chaikovskaia.  Optimization of a fleet of reconfigurable robots for logistics warehouses.  PhD thesis, Université Clermont Auvergne, France, 2023.
  * [7] M. Chaikovskaia, J.-P. Gayon, and M. Marjollet.  Sizing of a fleet of cooperative and reconfigurable robots for the transport of heterogeneous loads.  In 2022 IEEE 18th International Conference on Automation Science and Engineering, pages 2253–2258, 2022.
  * [8] E. G. Coffman, Jr., M. R. Garey, and D. S. Johnson.  An application of bin-packing to multiprocessor scheduling.  SIAM Journal on Computing, 7(1):1–17, 1978.
  * [9] M. R. Garey and D. S. Johnson.  Computers and Intractability: A Guide to the theory of NP-completeness.  1979\.
  * [10] R. L. Graham.  Bounds on multiprocessing timing anomalies.  SIAM Journal on Applied Mathematics, 17(2):416–429, 1969.
  * [11] S. Hartmann and D. Briskorn.  An updated survey of variants and extensions of the resource-constrained project scheduling problem.  European Journal of operational research, 297(1):1–14, 2022.
  * [12] D. S. Hochbaum and D. B. Shmoys.  Using dual approximation algorithms for scheduling problems: Theoretical and practical results.  In Procs. of FOCS, pages 79–89. IEEE Computer Society, 1985.
  * [13] D. Knop, M. Koutecký, and M. Mnich.  Combinatorial $n$-fold integer programming and applications.  Math. Program., 184(1):1–34, 2020.
  * [14] S. T. McCormick, S. R. Smallwood, and F. Spieksma.  A polynomial algorithm for multiprocessor scheduling with two job lengths.  Mathematics of Operations Research, 26(1):31–49, 2001.
  * [15] MecaBotiX.  https://www.mecabotix.com/, 2023.
  * [16] M. Mnich and R. van Bevern.  Parameterized complexity of machine scheduling: 15 open problems.  Comput. Oper. Res., 100:254–261, 2018.
  * [17] M. Mnich and A. Wiese.  Scheduling and fixed-parameter tractability.  Math. Program., 154(1-2):533–562, 2015.
  * [18] M. Yue.  On the exact upper bound for the multifit processor scheduling algorithm.  Annals of Operations Research, 24(1):233–259, 1990.