Sage Journals: Discover world-class research

Abstract

With the wide application of advanced information technology and intelligent equipment in the manufacturing system, the decisions of design and operation have become more interdependent and their integration optimization has gained great concerns from the community of operational research recently. This article investigates an optimization problem of integrating dynamic resource allocation and production schedule in a parallel machine environment. A meta-heuristic algorithm, in which heuristic-based partition, genetic-based sampling, promising index calculation, and backtracking strategies are employed, is proposed for solving the investigated integration problem in order to minimize the makespan of the manufacturing system. The experimental results on a set of random-generated test instances indicate that the presented model is effective and the proposed algorithm exhibits the satisfactory performance that outperforms two state-of-the-art algorithms from literature.

Keywords

Integration optimization parallel machine dynamic resource allocation scheduling nested partition method

Introduction

In manufacturing systems, there are usually existing two different categories of production activities.^1–7 One is the design activity such as allocating the resources into the production units to determine the production capacity. The other is the operation activity such as scheduling the jobs in the production units to satisfy the production demand. The decisions of design and operation activities are typically made independently. The decision-maker first determines the allocation plan of resources (workers, electric power, and so on) and then determines the schedule plan of jobs according to the allocated resources.^8–13 However, these two activities require to be closely related in practice. The available resources are always limited, and the allocation plan of resources in the production unit (or machine) can affect the efficiency of processing jobs. In recent years, the integrated resource allocation and production schedule problems have received more and more attention from the operational research (OR) community. The similar works that are termed as the scheduling problem with flexible resource constraints have been reported in literature.^14–17 It is noticeable that the most works only focus on the static resource allocation plan, in which the allocated resources in a machine always remain fixed during the whole production horizon. With the recent development of advanced information technology and intelligent equipment, such as manufacturing execution system (MES), industrial robots, and so on, the production process in the manufacturing system must be able to re-operate, even re-design dynamically. Therefore, this article aims at investigating the optimal integration of dynamic resource allocation and production schedule in a parallel machine manufacturing environment.

Parallel machine scheduling can usually be defined as a set of identical machines employed to process the jobs in parallel so as to optimize a given scheduling criterion.¹⁸ In general, this parallel machine scheduling problem can be broken down into two subproblems: first, assign each job to any of the machines and then determine the process sequence of jobs on each machine. Many real-world problems can be translated into parallel machine scheduling, for example, operation room scheduling in hospitals,¹⁹ gate assignment scheduling in airports,²⁰ and process scheduling in CPUs.²¹ It is noticeable that these studies only focused on the scheduling problem, neither involve in the allocation of resources. Daniels et al.^22,23 first broadened the scope of the traditional scheduling function to include both job sequencing and processing time control through allocating a flexible resource among the parallel machines. In their works, the processing time of each job was to depend on the amount of resource allocated to the associated machine. Parallel machine scheduling problems with resource allocation constraints had begun to gain more and more concerns in recent years.^24–26 Based on the distinct characteristics of resources, the relevant research works could be grouped into two categories. In the first category, processing of job was associated with the allocated amount of nonrenewable resource, for example, electric power or water. A constraint of the total amount or resource or an objective function in terms of resource cost was usually utilized when deciding job assignment among machines and jobs sequence on machines.^27–33 The second category focused on parallel machine scheduling under the allocation constraint of reusable and renewable resources.^34–37 Resource allocation among machines and jobs was known in advance, and thus, a schedule plan should include three decisions, that is, job assignment among machines, job sequence, and start time on machines. It is noticeable that the most works only concerned the allocation of resources among machines and jobs in a static way. In this static way, the resources always remained fixed once they were allocated upon a machine processing a job, or job assignment among machines always required to be known in advance.

In this article, a parallel machine scheduling problem that enables to allocate a reusable and renewable resource dynamically in a production horizon will be studied. In the investigated problem, integrated optimal decision of job assignment among machines, resource allocation among jobs, job sequence, and start time on machines will be considered simultaneously. A nested partition (NP) algorithm will be developed to deal with this complicated optimization problem effectively and efficiently. In the proposed algorithm, four special operations, including heuristic-based partition, genetic-based sampling, promising index calculation, and backtracking strategy, will be designed based on the problem characteristics.

The remainder of this article is organized as follows. Section “Problem statement” states the investigated problem and presents its mathematical model. Section “Solution method” introduces the proposed algorithm and gives its detailed design. Section “Experimental study” conducts the numeric experiments and analyzes the experimental results. Section “Conclusion” draws the conclusions with a brief outlook of the future work together.

Problem statement

In this section, we introduce a parallel machine scheduling problem with dynamic resource allocation. There are $n$ jobs that require to be processed on $m$ identical parallel machines. Processing of job on machine is always associated with an allocated resource that is reusable and renewable. There are multiple processing modes, any of which is corresponding to a given amount of resource allocation. The processing time of job is a function of the amount of resource that is allocated to this production process. The resource with a limited total amount can be allocated and re-allocated freely among all jobs in a production horizon. Each machine can process at most one job at any time. Each job is only allowed to process on one machine in one mode. Once a certain amount of resource is allocated to a job, it cannot be re-allocated to another job until processing of this job is finished. The goal is to determine job assignment among machines, resource allocation among jobs, job sequence, and start time on machines so as to minimize the makespan of this parallel machine manufacturing system.

Notations used are listed as follows:

Index sets:
$N$	job index set, $N = {1, 2, \dots, n}$ , where $n$ is the number of jobs.
$N'$	extended job index set, $N' = {0, 1, 2, \dots, n}$ , where 0 is a dummy job.
$M$	machine index set, $M = {1, 2, \dots, m}$ , where $m$ is the number of machines.
$K_{i}$	processing mode set of job $i$ , $K_{i} = {1, 2, \dots, s_{i}}$ , where $s_{i}$ is the number of processing modes of job $i$ .
Parameters:
$R$	the total amount of resource.
$r_{ik}$	the required amount of resource that job $i$ is processed in mode $k$ .
$p_{ik}$	the processing time of job $i$ is processed in mode $k$ .
$p_{i}$	the actual processing time of job $i$ .
$T$	upper bound of a schedule horizon.
$G$	a large constant.
Decision variables:
$C_{ij}$	the completion time of job $i$ on machine $j$ .
$x_{ijkt}$	$x_{ijkt} = 1$ if job $i$ immediately precedes job $h$ in mode $k$ at time $t$ ; and 0 otherwise.
$y_{ihj}$	$y_{ihj} = 1$ if job $i$ immediately precedes job $h$ on machine $j$ ; and 0 otherwise.

It is noted that the processing modes in $K_{i}$ are determined in advance. If $k_{1}, k_{2} \in K_{i}$ with $k_{1} < k_{2}$ , then $r_{i k_{1}} < r_{i k_{2}}$ and $p_{i k_{1}} > p_{i k_{2}}$ . This assumption makes sense with loss of generality because the more amount of resource that is allocated to a job can make this job’s processing time less. In a production process, dynamic resource allocation among jobs can be implemented through the varying of mode $k$ at time $t$ .

According to these notations and definitions, an integer programming model can be established as follows

min C_{max}

(1)

s.t.

\sum_{j \in M} \sum_{k \in K_{i}} p_{ik} \sum_{t = 0}^{T} x_{ijkt} = p_{i}, \forall i \in N

(2)

\sum_{j \in M} \sum_{k \in K_{i}} \sum_{t = 1}^{T} t \cdot x_{ijkt} = C_{i}, \forall i \in N

(3)

\sum_{j \in M} \sum_{k \in K_{i}} \sum_{t = 1}^{T} x_{ijkt} = 1, \forall i \in N

(4)

\sum_{i \in N} \sum_{j \in M} \sum_{k \in K_{i}} r_{ik} \sum_{t' = t}^{t + p_{ik} - 1} x_{ijkt'} \leq R, t \in {1, 2, \dots, T}

(5)

\sum_{j \in M} \sum_{i \in N', i \neq h} y_{ihj} = 1, \forall h \in N

(6)

\sum_{j \in M} \sum_{h \in N, i \neq h} y_{ihj} \leq 1, \forall i \in N

(7)

\sum_{h \in N} y_{0 hj} \leq 1, \forall j \in M

(8)

\sum_{h \in N', h \neq i, h \neq l} y_{ihj} \geq y_{hlj}, \forall h, l \in N, h \neq l, j \in M

(9)

C_{h} - C_{i} + G (1 - y_{ihj}) > p_{h}, \forall j \in M, \forall i \in N'

(10)

C_{max} = max_{\forall i \in N, \forall j \in M} {C_{ij}}

(11)

C_{i 0} = 0, C_{ij} \geq 0, \forall i \in N, \forall j \in M

(12)

x_{ijkt} \in {0, 1}, \forall i \in N, \forall j \in M, \forall k \in K_{i}, t \in {1, 2, \dots, T}

(13)

y_{ihj} \in {0, 1}, \forall i \in N', \forall h \in N, \forall j \in M

(14)

where equation (1) means that the objective function is to minimize the makespan. As shown in equation (11), the makespan of a schedule is equal to the maximum completion time of all jobs. Constraints (2) and (3) define the processing time and the completion time of job, respectively. Constraint (4) guarantees that each job must be processed on one machine in one mode. Constraint (5) ensures that the total amount of allocated resource at any time cannot exceed its limit. Constraint (6) stipulates that each job only has one predecessor on one machine. Constraint (7) guarantees that each job has only one immediately precedence job. Constraint (8) shows that each machine has only one dummy job. Constraint (9) defines the sequence relation of jobs on one machine. Constraint (10) means that each machine can only process one job at any time. The left constraints give the range of decision variables.

A general parallel machine scheduling problem with objective of minimizing the makespan has been proved to be NP-hard.³⁸ The investigated problem in this article is also NP-hard since more decisions, such as resource allocation among jobs and job start time on machines, have to be considered with the traditional schedule decisions together. Therefore, a meta-heuristic algorithm is proposed as an optimizer for solving this complicated parallel machine scheduling problem with dynamic resource allocation effectively in the next section.

Solution method

Meta-heuristic algorithm has been well known as one of best optimizers for the complex optimization problems.^39–41 NP is a new meta-heuristic algorithm introduced by Shi and Olafsson.⁴² It has been successfully applied to solve many complex optimization problems, for example, traveling salesman problem,⁴³ buffer allocation problem,⁴⁴ product design problem,⁴⁵ and production scheduling problems.^46,47

Basic algorithm framework

In NP algorithm, there are four operations, that is, partitioning, sampling, promising index calculation, and move. Let $Θ$ denotes a solution space for an optimization problem, $σ (k)$ is the most promising region in $k$ th iteration. The procedure of the NP method is described as follows:

Step 1: Partitioning. Partition the most promising region $σ (k)$ into $Q$ subregions $σ_{1} (k), σ_{2} (k), \dots, σ_{Q} (k)$ and aggregate the complementary region $Θ \ σ (k)$ into one region $σ_{Q + 1} (k)$ .

Step 2: Sampling. Randomly generate $q_{j}$ sample solutions from each of the region $σ_{j} (k)$ , $j = 1, 2, \dots, Q + 1$

x_{1}^{j}, x_{2}^{j}, \dots, x_{q_{j}}^{j}, j = 1, 2, \dots, Q + 1

Calculate the corresponding performance values

f (x_{1}^{j}), f (x_{2}^{j}), \dots, f (x_{q_{j}}^{j}), j = 1, 2, \dots, Q + 1

Step 3: Calculating the promising index. For each region $σ_{j}$ , $j = 1, 2, \dots, Q + 1$ , calculate the promising index as the best performance value of each region

I (σ_{j}) = min_{i = 1, 2, \dots, q_{j}} f (x_{i}^{j}), j = 1, 2, \dots, Q + 1

Step 4. Move. Calculate the promising region index with the best performance value

j_{k} = \arg min_{j = 1, 2, \dots, Q + 1} I (σ_{j})

If more than one region is equally promising, the tie can be broken arbitrary. If this index corresponds to a region that is a subregion of $σ (k)$ , that is, $j_{k} \leq Q$ , then let this region be the most promising region in the next iteration, that is, $σ (k + 1) = σ_{j_{k}} (k)$ . Otherwise, if the index corresponds to the complimentary region, that is, $j_{k} = Q + 1$ , and then backtrack to the previous most promising region, that is, $σ (k + 1) = σ (k + 1)$ .

By repeating Steps 1–4, the NP method can deal with an optimization problem effectively. If the most promising region includes only one solution, it stops and outputs the obtained solution and objective value. Next, NP algorithm combining with some heuristic rules and genetic algorithm (NP-HGA) is designed and discussed.

Solution representation

There are four decisions when solving the investigated problem, that is, job assignment among machines, resource allocation among jobs, jobs’ sequence, and start time on machines. A solution should represent them simultaneously, and thus, this study applies a permutation vector to denote a feasible solution. In this vector, each position denotes a job index and each element contains three parts that represent the schedule of its corresponding job. In detail, a solution can be represented by $s = {(r_{1}, t_{1}, j_{1}), (r_{2}, t_{2}, j_{2}), \dots, (r_{n}, t_{n}, j_{n})}$ , and it denotes the job $i$ starts to be processed on machine $j_{i}$ at time $t_{i}$ with $r_{i}$ unit resources.

NP partitions a feasible region of an optimization problem at its first iteration. This feasible region is named as initial feasible region. The initial feasible region can be a whole or partial solution space. The former can realize a global search that has to consume more computational cost, while the latter utilizes a local initial feasible region to ensure the solution quality with less computation cost. This study employs the latter approach and proposes a heuristic rule to produce an initial feasible region as follows. First, sort all jobs in the descending order as the processing time difference of their first and second modes and stored in $π$ . Second, choose $m$ jobs from $π$ by using a binary tournament selection approach based on their indexes, and the job with a smaller index is stored at each time, then delete these jobs from $π$ . Third, assign a unit resource to these jobs as their sequence until all resources are assigned. Finally, choose the earliest available machine to arrange these jobs as their sequence. By repeating the last three steps, we can generate a partial schedule where some jobs are fixed. This partial schedule with fixing 30% of jobs is chosen as an initial feasible region.

Partitioning operation

In NP-HGA, the partitioning operation is used to arrange one job based on the current promising region. It constructs a set of subregions, and each subregion is developed by determining the assignment, resource allocation, and start time of a job. If there is a promising region where $d$ jobs have been fixed, $Rm (n - d)$ subregions can be constructed by assigning each job to different machines and number of resources. It can be found that a great many subregions should be generated from a given region and enumerating them needs to cost much computational resource. To improve the efficiency of the partition method, this study proposes a heuristic rule where a job is assigned to the earliest available machine and its corresponding available time, and then, we only enumerate all feasible schedules that meet resource constraints on this machine. Let $σ$ denotes a promising region in the $k$ th iteration; then, the partition procedure is described as follows:

Input: current feasible region $σ (k)$ , unscheduled job set $N^{U} (σ (k))$ , schedule job set $N_{j}^{S} (σ (k))$ on machine $j$ , scheduled job set $N^{S} (σ (k))$ , $N^{S} (σ (k)) = ⋃_{j = 1}^{m} N_{j}^{S} (σ (k))$ , start time of scheduled job $t (σ (k))$ , number of scheduled job on machine $κ_{j} (σ (k))$ , $j = 1, 2, \dots, m$ .

Output: subregions of $σ (k)$ , that is, $σ_{1} (k)$ , $σ_{2} (k)$ , …, $σ_{Q} (k)$ , where $Q$ is the number of subregions, $Q = R \times (n - \sum_{j = 1}^{m} κ_{j} (σ (k))) = R \times \sum_{j = 1}^{m} | | N^{U} (σ (k)) | |$

Step 1: $π = N^{U} (σ (k))$ , $l = 1$ .

Step 2: Choose a job $i$ from $π$ , $π = π - {i}$ , $τ_{i} = K_{i}$ , $t = 0$ .

Step 3: Identify the earliest available machine $j^{*}$ and earliest available time $t_{j^{*}}$ .

Step 4: Determine the earliest schedule time $t'_{j^{*}}$ which meets $t'_{j^{*}} > t$ , $t = t'_{j^{*}}$ .

Step 5: Calculate the number of available resources $R_{{t'}_{j^{*}}}$ at time $t'_{j^{*}}$ and identify the available processing mode set $τ'_{i}$ at time $t'_{j^{*}}$ , $τ = τ - {τ'_{i}}$ .

Step 6: Determine the feasible schedules $(r_{i}, t'_{j^{*}}, j^{*})$ for job $i$ at time $t'_{j^{*}}$ , and construct the subregions as follows: (1) Choose a processing mode $q$ from $τ'_{i}$ , $τ'_{i} = τ'_{i} - {q}$ ; (2) Construct a subregion $σ_{l} (k)$ , $l = l + 1$ ; (3) If $τ'_{i} = \emptyset$ , go to Step 7; Otherwise return to (1).

Step 7: If $π \neq \emptyset$ , go to Step 2; Otherwise output subregions $σ_{1} (k)$ , $σ_{2} (k)$ , …, $σ_{Q} (k)$ , and then stop this procedure.

Sampling operation

Sampling operation aims to find the better solutions in a region which can represent this region’s promising index. This study designs a heuristic rule to generate a set of solutions, and then, a partheno genetic algorithm is employed to search a better solution to calculate the promising index of this region.

The heuristic rule is developed based on longest processing time first and it is described as follows:

Input: the feasible region in $k$ th iteration $σ (k)$ , unscheduled job set $N^{U} (σ (k))$ , scheduled job set $N_{j}^{S} (σ (k))$ , scheduled job set $N_{j}^{S} (σ (k))$ on machine $j$ , start time, and resource allocation of jobs $t (σ (k))$ and $r (σ (k))$ , scheduled job on machine $κ_{j} (σ (k))$ , a threshold value $u$ , $0 < u \leq 1$ .

Output: a feasible solution.

Step 1: $π = N^{U} (σ (k))$ , $τ = N^{U} (σ (k))$ , where $π$ is randomly sorted, and $τ$ is stored in the ascending order based on the processing time of jobs in the first mode.

Step 2: $a = π$ , and $b = τ$ , let $l (a)$ and $l (b)$ denote the position index of jobs in $a$ and $b$ , respectively. Let $i_{l (*)}$ denotes job index in position $l (^{*})$ .

Step 3: Identify the first available machine $j^{*}$ and its earliest available time $t_{j^{*}}$ .

Step 4: Calculate the number of available resources $R_{{t'}_{j^{*}}}$ at time $t_{j^{*}}$ .

Step 5: Generate a number $p$ from a uniform distribution (0, 1).

(1) If $ρ \leq u$ , assign job $i$ to machine $j^{*}$ as follows: (a) $i = i_{l (a)}$ , for $k = 1, 2, \dots, K_{i}$ , if $r_{ik} \leq R_{t_{j^{*}}}$ , then $x_{ik} = 1$ , otherwise $x_{ik} = 0$ . Let $P_{i} = \sum_{k = 1}^{| | K_{i} | |} (p_{ik} + x_{ik} = r_{ik})$ . For $h = 1, 2, \dots, K_{i}$ , calculate $f_{h} = (p_{ih} + x_{ih} \cdot r_{ih}) / P_{i}$ ; (b) Employ the roulette wheel method to choose a processing mode $g$ for job $i$ , then allocate $r_{l (a), g}$ resources to it; (c) If $r_{l (a), g} \leq R_{t_{j^{*}}}$ , let job $i$ be processed at time $t_{j^{*}}$ and go to (e), otherwise go to next; (d) Choose the next time point which is greater than $t_{j^{*}}$ and then let it replace $t_{j^{*}}$ , go to (c); (e) $a = a - {i_{l (a)}}$ , $b = b - {i_{l (a)}}$ .

(2) If $ρ > u$ , assign job $l (b)$ to machine $j^{*}$ and schedule it as (1).

Step 6: If $a = \emptyset$ and $b = \emptyset$ , then output the generated solution; Otherwise go to Step 3.

By repeating this heuristic rule, we can generate $N_{s}$ solutions that are stored in $P$ , and then, a partheno genetic algorithm is employed to refine them further. The partheno genetic algorithm only uses selection and mutation operators, and thus, it is simple and easy to implement.⁴⁸ It is described as follows: First, a tournament wheel selection approach is used to generate an individual;^49,50 Second, a mutation operator is employed to generate a neighborhood individual. By using them, we can generate $N_{s}$ new individuals which are stored in $P'$ . At last, we combine $P$ with $P'$ and choose the top best $N_{s}$ individuals as the next population. Based on the problem’s characteristics, we randomly change the assigned machine and number of allocated resources of an unscheduled job in the current subregion. By using this approach and through $I_{M}$ iterations, the best solution in $P$ is chosen for calculating the promising index of this subregion.

Index calculation and move operations

The promising index of subregions denotes their own probability that contains the optimal solution. A subregion with the best promising index is chosen as the promising region in the next iteration. Thus, it guides the algorithm’s search direction. In this study, the objective function value of the best solution found in sampling operation is taken as the promising index of its corresponding subregion. As this approach, we can calculate the promising index of all subregions.

Based on the above approach, NP-HGA can select a promising region. If one of the subregions has the best promising index, it moves to this subregion to perform the next iteration. If the complementary region has the best promising index, it indicates that the algorithm falls into a local optimal. Thus, a backtracking strategy is used to make the algorithm return to one of the previous searched regions. This study designs four backtracking strategies as follows: (1) backtrack to the previous region of the current most promising region; (2) backtrack to the initial promising region; (3) backtrack to the previous region containing the best solution found so far; and (4) backtrack to the previous region containing the best solution found in the complementary region.

Experimental study

To examine the performance of NP-HGA in solving the investigated problem, two state-of-the-art algorithms in literature are employed as its comparison algorithms. The hybrid nested partition (h-NP)⁴⁷ method was initially designed for the parallel machine scheduling problem in static resource allocation way, while master-slave genetic algorithm (MSGA)⁴⁹ was used to solve the scheduling problem with dynamic resource allocation in parallel machine manufacturing environment.

Test instances

The following method is used to generate a set of random test instances in the experiments. The number of machines is set to $m \in {3, 4, 5, 6, 7, 8, 9}$ , and the number of jobs is set to $n \in {10, 15, 24, 32, 36, 42, 56}$ . Then, there are seven different combinations, that is, $3 \times 10$ , $4 \times 15$ , $5 \times 24$ , $6 \times 32$ , $7 \times 36$ , $8 \times 42$ , and $9 \times 56$ . The amount of available resource in each combination is set to $R \in {m, m + 1, m + 2, m + 3}$ . Therefore, there are totally 28 test instances. In each instance, each job has three processing mode 1, 2, and 3. The amount of allocated resource in these three modes is 1, 2, and 3, respectively. The processing time of job in the first mode $p_{i 1}$ is generated from the uniform random distribution $U (10, 50)$ , and the processing times in the second and third mode is calculated according to equation (15), where $α$ is a coefficient that is equal to 0.6

p_{ik} = p_{i 1} \times (1 - α \times (1 - (1 / k)))

(15)

Parameter settings

The parameter settings of all algorithms are set as follows. In h-NP, the number of sampled solutions from each subregion is set to 20, $u$ is set to 0.8, and the mutation probability is set to 0.8. In MSGA, the population size of master and slave chromosome population is set to 10 and 20, respectively. The cross-over probability of slave chromosome is set to 0.55, and the mutation probability of the master and slave chromosomes is set to 0.15 and 0.35, respectively. In NP-HGA, $N_{s}$ and $I_{M}$ are both set to 10, and $u$ is set to 0.75. To make a fair comparison, the maximal allowable evaluation number is set to $1000 \times m \times n$ for all algorithms. It is noticeable that h-NP and NP-HGA are allowed to terminate if they achieve a subregion, where all jobs have been fixed, that is, a feasible and full schedule has been achieved.

Experimental results and discussions

In this section, we carry out three experiments to choose an effective backtracking strategy for NP-HGA in solving the investigated problem.

To examine the performance of four strategies, we choose an instance with 9 machines and 56 jobs. The experimental results are shown in Table 1, where “NP-HGA-X” means that the backtracking strategy $X \in {A, B, C, D}$ is used and “b-times” means the backtracking times with different strategies. It can be seen that strategy C performs a little better than the others because it can obtain smaller objective value and backtracking time. Backtracking strategy aims to guarantee NP to search for an optimal solution along a promising direction. It can correct this direction by returning to the most promising region found in the past once it detects that the current region is not the most promising region. Strategy C regards the previous region containing the best solution as the most promising region and backtracks to it. In fact, it fully utilizes the obtained search information in the past search process, and thus, it can achieve a better performance. Strategy A returns to the previous region of the current promising region. Nevertheless, the new promising region may still be an incorrect region because this strategy does not fully use the obtained search information. Strategy B returns to the initial feasible region, which means that the algorithm restarts and does not employ any search information, and thus, its performance is not very good. Strategy D backtracks to the previous region containing the best solution found in the complementary region. Although it uses the information in the past search process, the best solution located in complementary region maybe not the best solution found so far. Thus, the complementary region may not be the most promising region. Therefore, the backtracking strategy C can achieve a better result, and it is chosen and employed in NP-HGA in the following experiments.

Table 1.

Comparison of four backtracking strategies.

	Algorithm	$C_{max}$	b-times
$R = 9$	NP-HGA-A	180.24	24.80
	NP-HGA-B	179.73	67.45
	NP-HGA-C	177.45	20.93
	NP-HGA-D	178.10	22.02
$R = 10$	NP-HGA-A	175.72	32.29
	NP-HGA-B	178.25	57.92
	NP-HGA-C	166.18	21.80
	NP-HGA-D	170.25	28.56
$R = 11$	NP-HGA-A	166.42	45.19
	NP-HGA-B	170.20	62.39
	NP-HGA-C	154.62	21.77
	NP-HGA-D	160.34	27.67
$R = 12$	NP-HGA-A	158.42	53.46
	NP-HGA-B	159.92	75.73
	NP-HGA-C	145.70	22.29
	NP-HGA-D	152.67	26.46

NP-HGA: nested partition algorithm combining with some heuristic rules and genetic algorithm.

The second experiment chooses an instance in Daniels et al.³⁴ to compare the NP-HGA with the static resource allocation case by using h-NP. In this instance, there are 4 machines and 15 jobs. Each job has three processing modes 1, 2, and 3 that need 1, 2, and 3 unit amount of resource, respectively. The processing time of job in the three processing modes is shown in Table 2. Figure 1 shows the Gantt charts via h-NP and NP-HGA, respectively. In this figure, a symbol “ $i^{k}$ ” means job $i$ is processed with the $k$ th processing mode. From the two Gantt charts, we can find that the makespan of the static case obtained by h-NP and dynamic case obtained by NP-HGA is 97. It can be found that the completion time of machines in the static case is 97, while in the dynamic case, there is one machine whose completion time is earlier. Hence, we can conclude that NP-HGA can effectively utilize the given resources. It demonstrates that the dynamic case has more superiority than the static one. The result means that the dynamic resource allocation can utilize the resources more efficiently, and NP-HGA can find a better result. In addition, a decision-maker should choose dynamic resource allocation when they have to deal with a parallel machine scheduling with additional resource allocation.

Table 2.

The processing time of jobs in the three processing modes.

Job	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$p_{i 1}$	37	34	35	41	43	20	31	18	19	24	46	19	28	32	42
$p_{i 2}$	26	24	25	29	30	14	22	13	13	17	32	13	20	22	29
$p_{i 3}$	22	20	21	25	26	12	19	11	11	14	28	11	17	19	25

Figure 1.

Illustration of the experimental results via Gantt charts: (a) h-NP, (b) NP-HGA.

In the third experiment, we compare NP-HGA with h-NP and MSGA by using all test instances. For each test instance, each algorithm executes 20 times independently. The average value (mean) and standard deviation (SD) are recorded to evaluate their performance. In addition, equation (16) is employed to compare NP-HGA with MSGA

r a t i o = \frac{C_{\max}^{M S G A} - C_{\max}^{N P - H G A}}{C_{\max}^{M S G A}} \times 100 %

(16)

The experimental results of the third experiment are shown in Table 3, where a symbol “ $m \times n$ ” denotes that the number of machines and jobs is $m$ and $n$ , respectively, and $R$ represents the number of available resources for a given instance. Note that h-NP gives the experimental results on the static resource allocation case, while the experimental results of MSGA and NP-HGA are the dynamic resource allocation case.

Table 3.

Experimental results of three algorithms.

$m \times n$	$R$	h-NP		MSGA		NP-HGA		b-times	Ratio (%)
		Mean	SD	Mean	SD	Mean	SD
$3 \times 10$	3	96.95	2.96	96.72	2.98	93.21	2.76	6.43	3.63
	4	83.22	1.94	83.73	3.01	79.20	2.24	8.21	5.41
	5	73.76	1.87	73.72	2.85	69.12	2.62	7.02	6.24
	6	67.98	2.93	66.42	2.81	62.24	1.69	9.09	10.34
$4 \times 15$	4	104.67	1.80	103.00	2.78	98.25	2.57	8.47	6.43
	5	95.21	1.62	94.75	2.01	87.87	1.51	6.02	7.26
	6	85.52	1.52	85.95	1.97	79.24	1.86	8.99	7.81
	7	78.54	2.07	78.64	2.54	76.24	2.09	7.44	3.05
$5 \times 24$	5	142.23	1.74	142.10	3.12	136.45	2.46	8.49	3.98
	6	130.12	2.17	129.37	2.88	125.29	1.82	10.71	3.15
	7	120.31	2.35	119.42	2.76	114.91	2.49	15.66	3.78
	8	110.42	2.92	109.20	3.12	105.56	1.41	14.47	3.33
$6 \times 32$	6	154.24	2.50	153.23	3.01	150.69	2.27	11.38	1.66
	7	143.76	2.86	142.56	2.76	138.53	2.28	17.79	2.83
	8	133.43	2.53	131.72	2.47	128.18	2.53	12.63	2.69
	9	123.89	1.91	120.07	3.01	116.62	2.69	18.44	2.87
$7 \times 36$	7	147.21	2.75	145.10	2.55	142.16	1.97	14.79	2.03
	8	141.34	1.90	136.59	2.22	132.16	2.28	16.71	3.24
	9	131.24	2.59	127.54	3.00	123.97	1.61	14.77	2.80
	10	125.35	2.81	120.76	2.35	114.61	1.82	19.82	5.09
$8 \times 42$	8	155.62	1.52	153.11	2.72	150.33	1.65	16.38	1.82
	9	146.67	2.61	142.32	2.12	138.42	1.93	24.36	2.74
	10	138.65	1.55	134.76	2.89	129.45	1.95	18.23	3.94
	11	132.71	1.68	125.70	2.47	119.59	2.78	18.80	4.86
$9 \times 56$	9	181.46	1.86	179.80	2.87	177.45	1.99	20.93	1.31
	10	172.67	2.72	169.54	2.91	166.18	1.80	21.80	1.98
	11	165.29	2.12	159.09	3.08	154.62	2.57	21.77	2.81
	12	157.64	2.82	149.67	2.88	145.70	2.23	22.29	2.65

h-NP: hybrid nested partition; MSGA: master-slave genetic algorithm; NPHGA: nested partition algorithm combining with some heuristic rules and genetic algorithm; SD: standard deviation.

From the experimental results, we can find that NP-HGA can achieve the better results on all instances than those of h-NP. MSGA also performs better than h-NP in most of the instances. The results indicate that the dynamic resource allocation way is better than the static allocation one. In addition, we can find that NP-HGA outperforms MSGA in all instances by comparing their mean, standard deviation, and ratio values. This demonstrates that dynamic resource allocation on parallel machine scheduling can efficiently utilize the limited resources, and NP-HGA has a better performance in solving the investigated problem.

To evaluate the algorithms’ performance in terms of computational time, the average computational time is examined when solving a test instance with different amounts of resource, and their computational time is shown in Table 4. Because the dynamic resource allocation case is more complex than the static one, the computational time of MSGA and NP-HGA consumes more time than h-NP. By comparing NP-HGA with MSGA, we can find that NP-HGA uses less time than MSGA in all instances.

Table 4.

Comparison of the algorithms’ computational time.

$m \times n$	Computational time (s)
	h-NP	MSGA	NP-HGA
$3 \times 10$	0.06	2.25	2.20
$4 \times 15$	0.08	5.98	5.16
$5 \times 24$	0.30	14.32	13.27
$6 \times 32$	1.02	44.27	42.16
$7 \times 36$	1.98	76.86	68.29
$8 \times 42$	3.27	113.34	98.20
$9 \times 56$	7.81	206.57	188.18

h-NP: hybrid nested partition; MSGA: master-slave genetic algorithm; NP-HGA: nested partition algorithm combining with some heuristic rules and genetic algorithm.

By conducting the above experiments and analyzing the experimental results, we can find that NP-HGA is a better solver in dealing with the parallel machine scheduling problem with dynamic resource allocation. NP-HGA is designed by introducing some special strategies for the investigated problem such as a heuristic-based partition, genetic-based sampling, promising index calculation, and backtracking approaches. These strategies do strengthen and balance the algorithm’s exploration and exploitation abilities and, thus, make the proposed algorithm perform better in solving the investigated problem.

Conclusion

This study investigates dynamic resource allocation in a parallel machine scheduling problem with objective of minimizing the makespan. To deal with it effectively, this study designs a nest partition algorithm that employs several specially designed operations, that is, heuristic-based partition, genetic-based sampling, promising index calculation, and backtracking strategies based on the problem characteristics. Numerical experiments are carried out on a set of random-generated test instances, and algorithm comparisons are made among the proposed algorithm and two state-of-the-art peer algorithms in literature. Experimental results demonstrate that dynamic resource allocation is much better than the static one, and the proposed algorithm performs better in solving the investigated problem.

For the future work, it is very necessary to extend the single time-related objective into multi-objective models that can take the cost- and revenue-oriented objectives into account together to help decision-makers find a flexible schedule plan. It is also an interesting work to design more efficient meta-heuristic algorithms to cope with the complicated parallel machine scheduling problems with dynamic resource allocation.

Footnotes

Handling Editor: James Baldwin

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is supported partly by National Natural Science Foundation of China (NSFC) under Grant No. 61703290, No. 71671032 and No. 61703220; the Natural Science Fund Guidance Program of Liaoning Province under Grant No. 2019-ZD-0478; the Fundamental Research Funds for the Central Universities Grant No. N160402002 and No. N180408019.

ORCID iD

Hongfeng Wang

References

Cui

, et al. A proactive approach to solve integrated production scheduling and maintenance planning problem in flow shops. Comput Ind Eng 2018; 115: 342–353.

Ding

Wang

, et al. Two-objective stochastic flow-shop scheduling with deteriorating and learning effect in Industry 4.0-based manufacturing system. Appl Soft Comput 2018; 68: 847–855.

Gao

Suganthan

Pan

, et al. Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives. J Intell Manuf 2016; 27: 363–374.

Gao

Wang

Luo

, et al. Discrete harmony search algorithm for scheduling and rescheduling the reprocessing problems in remanufacturing: a case study. Eng Optimiz 2018; 50: 965–981.

Pan

Gao

, et al. Effective metaheuristics for scheduling a hybrid flowshop with sequence-dependent setup times. Appl Math Comput 2017; 303: 89–112.

Ruiz

Pan

Naderi

Iterated greedy methods for the distributed permutation flowshop scheduling problem. Omega 2019; 83: 213–222.

Tian

Fathollahi-Fard

, et al. Stochastic multi-objective modelling and optimization of an energy-conscious distributed permutation flow shop scheduling problem with the total tardiness constraint. J Clean Prod 2019; 226: 515–525.

Expósito-Izquierdo

Angel-Bello

Melián-Batista

, et al. A metaheuristic algorithm and simulation to study the effect of learning or tiredness on sequence-dependent setup times in a parallel machine scheduling problem. Expert Syst Appl 2019; 117: 62–74.

Fanjul-Peyro

Ruiz

Perea

Reformulations and an exact algorithm for unrelated parallel machine scheduling problems with setup times. Comput Oper Res 2019; 101: 173–182.

10.

Wang

Huang

Integrated scheduling for a distributed manufacturing system: a stochastic multi-objective model. Enterp Inform Syst 2019; 13: 557–573.

11.

Gao

Pan

QK.

A shuffled multi-swarm micro-migrating birds optimizer for a multi-resource-constrained flexible job shop scheduling problem. Inform Sci 2016; 372: 655–676.

12.

Safarzadeh

Niaki

STA

. Bi-objective green scheduling in uniform parallel machine environments. J Clean Prod 2019; 217: 559–572.

13.

Wang

Alidaee

Unrelated parallel machine selection and job scheduling with the objective of minimizing total workload and machine fixed costs. IEEE Trans Autom Sci Eng 2018; 15: 1955–1963.

14.

Figielska

Scheduling in a two-stage flowshop with parallel unrelated machines at each stage and shared resources. Comput Ind Eng 2018; 126: 435–450.

15.

Duan

Sang

, et al. An efficient optimization algorithm for resource-constrained steelmaking scheduling problems. IEEE Access 2018; 6: 33883–33894.

16.

Sun

Geng

Wang

, et al. Convex resource allocation scheduling in the no-wait flowshop with common flow allowance and learning effect. Int J Prod Res 2019; 57: 1873–1891.

17.

Pei

Liu

Fan

, et al. A hybrid BA-VNS algorithm for coordinated serial-batching scheduling with deteriorating jobs, financial budget, and resource constraint in multiple manufacturers. Omega 2019; 82: 55–69.

18.

Cheng

Chu

Zhou

MC.

An improved model for parallel machine scheduling under time-of-use electricity price. IEEE Trans Autom Sci Eng 2018; 15: 896–899.

19.

Aringhieri

Landa

Soriano

, et al. A two level metaheuristic for the operating room scheduling and assignment problem. Comput Oper Res 2015; 54: 21–34.

20.

Narciso

Piera

MA.

Robust gate assignment procedures from an airport management perspective. Omega 2015; 50: 82–95.

21.

Singh

Goyal

Batra

An optimized round robin scheduling algorithm for CPU scheduling. Int J Comput Sci Eng 2010; 2: 2383–2385.

22.

Daniels

Hoopes

Mazzola

JB.

Scheduling parallel manufacturing cells with resource flexibility. Manage Sci 1996; 42: 1260–1276.

23.

Daniels

Hoopes

Mazzola

JB.

An analysis of heuristics for the parallel-machine flexible-resource scheduling problem. Ann Oper Res 1997; 70: 439–472.

24.

Ding

Song

Zhang

, et al. Parallel machine scheduling under time-of-use electricity prices: new models and optimization approaches. IEEE Trans Autom Sci Eng 2016; 13: 1138–1154.

25.

Györgyi

Kis

Approximation schemes for parallel machine scheduling with non-renewable resources. Eur J Oper Res 2017; 258: 113–123.

26.

Wang

Lin

SC.

Selection of cutting conditions for power constrained parallel machine scheduling. Robot Comput Int Manuf 2017; 43: 105–110.

27.

Chen

ZL.

Simultaneous job scheduling and resource allocation on parallel machines. Ann Oper Res 2004; 129: 135–153.

28.

Hsieh

Yang

DL.

Decision support for unrelated parallel machine scheduling with discrete controllable processing times. Appl Soft Comput 2015; 30: 475–483.

29.

Hsu

Yang

DL.

Unrelated parallel-machine scheduling with position-dependent deteriorating jobs and resource-dependent processing time. Optim Lett 2014; 8: 519–531.

30.

Oron

Scheduling controllable processing time jobs with position-dependent workloads. Int J Prod Econ 2016; 173: 153–160.

31.

Shioura

Shakhlevich

Strusevich

VA.

Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times. Math Program 2015; 153: 495–534.

32.

Yang

Cheng

TCE

Yang

SJ.

Parallel-machine scheduling with controllable processing times and rate-modifying activities to minimise total cost involving total completion time and job compressions. Int J Prod Res 2014; 52: 1133–1141.

33.

Yeh

Chuang

Lee

WC.

Uniform parallel machine scheduling with resource consumption constraint. Appl Math Model 2015; 39: 2131–2138.

34.

Daniels

Stella

Scott

Heuristics for parallel-machine flexible-resource scheduling problems with unspecified job assignment. Comput Oper Res 1999; 26: 143–155.

35.

Afzalirad

Shafipour

Design of an efficient genetic algorithm for resource-constrained unrelated parallel machine scheduling problem with machine eligibility restrictions. J Intell Manuf 2018; 29: 423–437.

36.

Fanjul-Peyro

Perea

Ruiz

Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources. Eur J Oper Res 2017; 260: 482–493.

37.

Zheng

Wang

A two-stage adaptive fruit fly optimization algorithm for unrelated parallel machine scheduling problem with additional resource constraints. Expert Syst Appl 2016; 65: 28–39.

38.

Lenstra

Kan

AHGR

Brucker

Complexity of machine scheduling problems. Ann Discret Math 1997; 1: 343–362.

39.

Ding

Yang

Jin

, et al. Generalized multi-tasking for evolutionary optimization of expensive problems. IEEE Trans Evolut Comput 2019; 23: 44–58.

40.

Yang

Ding

Jin

, et al. Multitasking multiobjective evolutionary operational indices optimization of beneficiation processes. IEEE Trans Autom Sci Eng 2019; 16: 1046–1057.

41.

Zhou

Guo

, et al. Scheduling dual-objective stochastic hybrid flow shop with deteriorating jobs via bi-population evolutionary algorithm. IEEE Trans Syst Man Cyb. Epub ahead of print 16 April 2019. DOI: 10.1109/TSMC.2019.2907575.

42.

Shi

Olafsson

Nested partitions method for global optimization. Oper Res 2000; 48: 390–407.

43.

Shi

Olafsson

Sun

New parallel randomized algorithms for the traveling salesman problem. Comput Oper Res 1998; 26: 371–394.

44.

Shi

Men

Optimal buffer allocation in production lines. IIE Trans 2003; 35: 1–10.

45.

Shi

Olafsson

Chen

A new hybrid optimization algorithm. Comput Ind Eng 1999; 36: 409–426.

46.

Jiang

Tian

, et al. Job scheduling and resource allocation in parallel-machine system via a hybrid nested partition method. IEEJ Trans Electr Electr Eng 2019; 14: 597–604.

47.

Shi

Olafsson

Chen

An optimization framework for product design. Manage Sci 2001; 47: 1681–1692.

48.

Yang

, et al. Electric vehicle route optimization considering time-of-use electricity price by learnable partheno-genetic algorithm. IEEE Trans Smart Grid 2015; 6: 657–666.

49.

Lei

Zheng

Guo

XP.

A shuffled frog-leaping algorithm for flexible job shop scheduling with the consideration of energy consumption. Int J Prod Res 2017; 55: 3126–3140.

50.

Wang

Tian

, et al. Two-agent stochastic flow shop deteriorating scheduling via a hybrid multi-objective evolutionary algorithm. J Intell Manuf 2019; 30: 2257–2272.

A meta-heuristic algorithm for integrated optimization of dynamic resource allocation planning and production scheduling in parallel machine system

Abstract

Keywords

Introduction

Problem statement

Solution method

Basic algorithm framework

Solution representation

Partitioning operation

Sampling operation

Index calculation and move operations

Experimental study

Test instances

Parameter settings

Experimental results and discussions

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References