1 Introduction

The parallel machine scheduling problem is a generalization of the single machine scheduling problem. Many production environments consist of several stages or workcenters, each with a number of machines working in parallel (Pinedo 2009). The parallel machine scheduling problem is significant because it is a common phenomenon in real life and a subproblem of multistage complex problems.

Parallel machine scheduling is one of the most studied problems in the scheduling literature. This problem is usually divided into three main classes based on the characteristics of processing time in the machines (Pinedo 2011): identical parallel machines, uniform parallel machines and unrelated parallel machines. Our problem is an identical parallel machine scheduling problem. Identical parallel machine scheduling problems can be studied along with different constraints. In this study, we consider an identical parallel machine scheduling problem with constraints of sequence-dependent setup time, machine eligibility and multiple copies of shared resources. Studies on parallel machine scheduling with each of these constraints are briefly discussed below in a separate paragraph.

The setup time is a period required to prepare a machine for processing. There are many studies on identical parallel machine scheduling problems with sequence-dependent setup times. In these studies, the objective of the problem is generally to minimize the makespan (Arnaout 2010; Montoya-Torres et al. 2009; Montoya-Torres et al. 2010; Kim and Kim 2011). Chung et al. (2009) analyzed a scheduling problem with job-cluster processing time, machine capacity and daily production target volumes on a polyimide printing process operation. They proposed a mixed-integer linear programming (MIP) model. The problem is also transformed into a multiple tour maximum collection problem. Driessel and Moench (2009) discussed an identical parallel machine scheduling problem in semiconductor manufacturing and considered ready times of the jobs, precedence constraints and sequence-dependent setup times. They suggested a variable neighborhood search scheme for the problem. The proposed approach was compared to heuristics based on the apparent tardiness cost of setups and the ready time dispatching rule. Li et al. (2010) considered an identical parallel machine scheduling problem with release date and due date. The objective function of the problem was to minimize the makespan and total tardiness. They developed a 0-1 mixed-integer program and a genetic algorithm (GA) with a fuzzy logic controller. Driessel and Moench (2011) obtained an initial solution for a variable neighborhood search. The entire scheme, with the initial solution obtained by the apparent tardiness cost with setups and ready times, was also fast. Lin et al. (2011) studied an identical parallel machine scheduling problem with sequence-dependent setup times and job release dates. The objective was to minimize the maximum lateness. They developed an improved iterated greedy heuristic and compared it with the basic iterated greedy heuristic. Turker and Sel (2011) analyzed a scheduling problem on two identical parallel machines with sequence-dependent setup times and setup operations. The objective was to minimize the makespan. They proposed an algorithm combining a genetic algorithm and a tabu search. Gokhale and Mathirajan (2012) addressed a scheduling problem with release times and machine eligibility restrictions for minimizing the total weighted flow time. They proposed a mathematical model and a number of heuristic algorithms to solve the problem. Park et al. (2012) took into account a parallel machine scheduling problem with job splitting and sequence-dependent major/minor setup times. They proposed heuristic algorithms for minimizing total tardiness. The performance of the proposed heuristics was compared with that of three previous algorithms in the literature. Li et al. (2012) developed two meta-heuristics (FLC-NSGA-II and FLC-SPEA-II) based on the traditional NSGA-II and SPEA-II for a parallel machine scheduling problem. They considered a multiobjective optimization problem to minimize the makespan and the total tardiness. Their experimental results showed the advantage of the proposed FLC-NSGA-II algorithm compared to NSGA-II and FLC-SPEA-II. Joo and Kim (2012) proposed two meta-heuristic algorithms for a parallel machine scheduling problem with ready times, due times and sequence-dependent setup times. The optimal solution was investigated with a mathematical model, and the performances of the developed meta-heuristic algorithms were evaluated with optimal solutions. Gedik et al. (2016) examined a parallel machine scheduling problem with setup times and time windows. Each job had a profit and cost. They proposed a constraint programming model and logic-based Benders algorithm to maximize total profit. The models were tested on a real-life case study by the U.S. Army Corps of Engineers.

Some machines are incapable of processing a particular job. This is referred to as machine eligibility restriction in the scheduling literature. There are also studies on identical parallel machine scheduling problems with machine eligibility restrictions. For example, Alagoz and Azizoglu (2003) analyzed a rescheduling problem in parallel machine environments under machine eligibility constraints. Their objective was to minimize total flow time, and they presented an optimizing algorithm. Eliiyi and Azizoglu (2009) considered an identical parallel machine scheduling problem with machine-dependent job weights. The objective was to maximize the total weight of the processed jobs. They presented a branch and bound algorithm and obtained successful results for large-sized problems. Additionally, Su et al. (2011) addressed an identical parallel machine scheduling problem with job deadlines and machine eligibility constraints to minimize the total job completion time. A heuristic and a branch and bound algorithm was developed to solve the problem. The proposed heuristic generated a good-quality schedule in a reasonable time. Finally, Lee et al. (2013) provided a brief overview of online scheduling in parallel machine environments with machine eligibility constraints with an objective function to minimize makespan. They surveyed different parallel machines and various types of machine eligibility restrictions.

In real-life problems, resources are used to produce products. Generally, jobs share these resources. To obtain an efficient schedule, this case must be considered. Although the use of resources is important for parallel machine scheduling problems, few studies have considered resources. For example, Li et al. (2011) recently proposed a simulated annealing algorithm to minimize makespan for an identical parallel machine scheduling problem. The processing times were controllable by consumed resources, and the total resource consumption was limited. Edis et al. (2012) addressed a real-life problem that required the simultaneous scheduling of jobs and operators over parallel machines. The operators were responsible for monitoring the machines, unloading the parts and trimming extra material. They proposed integer and constraint programming models for minimizing the completion time of the last job. Additionally, Ruiz and Andrés-Romano (2011) considered an unrelated parallel machine scheduling problem and job sequence-dependent setup times. The duration of the setup times depended on assignable resources. They developed a mixed-integer programming model to minimize total completion time and the total amount of resources assigned. Edis and Ozkarahan (2012) investigated a resource-constrained identical parallel machine scheduling problem with machine eligibility restrictions. They developed three optimization models: an integer programming model (IP), a constraint programming model (CP) and a combined IP/CP model. Edis and Ozkarahan (2011) presented mathematical models of static and dynamic parallel machine flexible resource scheduling (PMFRS) and unspecified PMFRS problems. In this problem, additional flexible resources could be freely allocated to any jobs and/or any machines. They proposed an integer programming-based constraint programming approach for large-sized dynamic PMFRS and UPMFRS problems. Fanjul-Peyro et al. (2017) focused on unrelated parallel machine scheduling problems with additional resource constraints in which the number of resources depends on machine and job. First, the authors proposed two linear programming models. Because of the NP-hard nature of the problem, they combined matheuristic strategies with each of the two mathematical models and demonstrated the success of the algorithms using computational tests. Afzalirad et al. (2016) addressed an unrelated parallel machine scheduling problem with resource constraints, sequence-dependent setup times, different release dates, machine eligibility and precedence constraints. The considered problem is the implementation of a real-life problem that is a block erection scheduling problem in a shipyard. The authors present a model and two new meta-heuristics. The results are discussed.

Using the three-field classification, IPMS–SMS is denoted in the scheduling literature as Pm|sjk, Mj, shared resource| \( \mathop \sum \nolimits w_{j} C_{j} \), where j and k indicate jobs, Pm and \( \mathop \sum \nolimits w_{j} C_{j} \) denote identical parallel machines and the total weighted completion times, respectively. No relevant previous study has considered these three constraints: sequence-dependent setup times (sjk), machine eligibility restrictions (Mj) and multiple copies of shared resources. Similar to that of Edis and Ozkarahan (2011), our motivation is the scheduling of injection molding machines in factory manufacturing plastic parts. Our problems are similar to those in their study, but there are three important differences: (1) they did not consider sequence-dependent setup times, but we did; (2) to cope with resource constraint, they assume that all the jobs used the same mold, assigned to the same machine consecutively, but as this assumption may hamper a search for better solutions, there is no such assumption in our study; and (3) a time index was used in a description of their decision variable. Therefore, when the scheduling horizon increases, the number of decision variables gradually increases, even if the number of jobs is fixed. On the other hand, the number of decision variables depends on the number of jobs in our study.

In this study, MIP models are proposed for IPMS-SMS. When the number of machines is two and the objective is to minimize the total weighted completion times, the parallel machine scheduling problem is NP-hard (Pinedo 2011). Although it is possible to find optimal solutions using mathematical models, this approach may require an enormous amount of computation time with increasing problem size. A large number of articles presented mathematical models of an investigated parallel machine scheduling problem. However, most of these articles used heuristic or meta-heuristic approaches to tackle the problems. In recent years, the genetic algorithm has been used as a significant meta-heuristic approach (Liu and Wu 2003; Chaudhry and Drake 2009; Chan et al. 2011; Keskinturk et al. 2012). However, if we want to use the GA in the case with a shared resource use, it is not sufficient to merely determine the job sequence for computing the value of the objective function (the fitness value). In addition, if jobs using a shared resource are scheduled at the same time, determining which resource will primarily use the shared resource is also necessary. In other words, the stage of determining the value of the objective function is also a matter of decision. Therefore, if we want to use a GA to solve this problem, a solution algorithm should be developed for computing the objective function. The proposed matheuristic is a GA using a mathematical model to determine the value of the objective function. Since the optimal value of the objective function can be found, better solutions can be obtained for a classical GA with fewer population and generation sizes.

The remainder of this paper is organized as follows: In Sect. 2, the problem definition and proposed mathematical models are given. The proposed matheuristic is introduced in Sect. 3. Test problems and computational results are represented in Sect. 4. Finally, Sect. 5 summarizes conclusions and recommendations for future research.

2 Problem definition and mathematical models of the problem

The scheduling of jobs is a major and difficult problem for most plastic parts manufacturers. Our motivation is scheduling plastic injection molding machines in the Boyplast plastic factory. This factory produces several plastic parts for electrical home appliance manufacturers.

There are three significant characteristics that should be considered in the injection machine scheduling problem: (1) production of a plastic part using an injection molding machine is a single-stage production. Each job can be processed with the same processing time on any one of the machines that belongs to the given subset. Thus, injection molding machines are identical machines that operate in parallel. To produce a product in an injection molding machine, the relative mold has to be fixed to it. All molds may not be fixed to all of the machines due to technical conditions. For instance, for a mold to be fixed to the injection molding machine, its width and length must be shorter than the column space, and the mold depth must be suitable for the closing space of the machine. Therefore, machine eligibility restrictions should be considered. (2) Products with the same form in different colors are considered different products. Therefore, it is possible to have different products using the same mold. Molds are shared resources of jobs. Jobs using the same mold cannot be scheduled simultaneously. However, if there are multiple copies of the mold, jobs can be simultaneously scheduled up to the number of copies. (3) Switching from the production of a certain product to another requires setup times. Setup times cover the changing of molds or the preparation of raw materials and paint mixtures, if necessary. Therefore, setup times are short for similar jobs. If similar jobs are not assigned to the same machines, the total setup time needed for production may increase significantly. For example, if the previous job used a light color, the setup time is short, but if the previous job has a dark color, the setup time can be much longer. Therefore, setup times are dependent on the job sequence.

After all, an identical parallel machine scheduling problem have three significant characteristics of injection machines: sequence-dependent setup times, machine eligibility restrictions and multiple copies of shared resources are considered. Two MIP models are proposed for the considered problem. The objective of the models is to minimize the total weighted completion time.

The presented MIP models are based on the following assumptions:

  1. (1)

    All parts are available for processing at time zero.

  2. (2)

    A machine can process one job at a time at most.

  3. (3)

    Machines are available for the scheduling horizon.

  4. (4)

    Preemption of the jobs is not allowed.

  5. (5)

    All processing and setup times of the jobs are deterministic.

  6. (6)

    Each job needs a resource to produce. Some jobs use the same resources, but a resource can be used by one job at a time at most.

  7. (7)

    There are different types of resources, and each type of resource may have copies.

The IPMS-SMS problem takes the following sets:

N = {1, 2, …, n} jobs set and

n  refers number of jobs to be processed;

L = {1, 2, …, m} machines set and

m denotes number of machines;

R = {1, 2, …, g} resources set and

g refers number of resource types which required processing of jobs at machines.

We will also use the following indices, parameters and decision variables.

Indices:

i, j and q ∈ N are indices to denote a job.

l ∈ L is the index to denote a machine.

k ∈ N is the index to denote the position of a job in the sequence of its machine.

r ∈ R is the index to denote a resource.

Parameters:

n: number of jobs

m: number of machines

g: number of resource types

pj: processing time of job j

M: a large positive number

hj: setup time of job j is first in the sequence

sij: sequence-dependent setup time between job i and job j

fr: number of available resources of type r

wj: weight of job j

resjr: \( \left\{ {\begin{array}{ll} {1,} & \quad {{\text{if resource }}r {\text{required by job }}j} \\ {0,} & \quad {\text{otherwise}} \\ \end{array} } \right. \)

bjl: \( \left\{ {\begin{array}{ll} {1,} & \quad {{\text{if job }}j {\text{can be processed on machine }}l } \\ {0,} & \quad {\text{otherwise}} \\ \end{array} } \right. \)

Decision variables:

Cj: completion time of job j

aj: starting time of job j

xjkl: \( \left\{ {\begin{array}{ll} {1,} & \quad {{\text{if job }}j {\text{is scheduled in }}k{\text{th order in machine}} l} \\ {0,} & \quad {\text{otherwise}} \\ \end{array} } \right. \)

$$ \lambda_{jl} :\left\{ {\begin{array}{ll} {1,} & \quad { {\text{if at least one other job that uses the same resource is scheduled in machine}} l }\\ & \quad {{\text{while job }}j {\text{is processing, }} } \\ {0,} & \quad {\text{otherwise}} \\ \end{array} } \right. $$

e1jq, e2jq, e3jq, e4jq: 0-1 integer decision variables for ensuring particular constraints

Objective function:

$$ \hbox{min} z = \mathop \sum \limits_{j = 1}^{n} w_{j} C_{j} $$
(1)

Objective (1) represents the minimization of the total weighted completion time. It is equal to the sum of the values that are obtained by multiplying completion time and weight for each job.

The constraints of the presented MIP model are explained in detail in the following parts:

$$ C_{j} + M*\left( {1 - x_{jkl} } \right) \ge p_{j} + h_{j} \quad \forall j,k,l \,\,\,\,\,\,k = 1 $$
(2)
$$ C_{j} + M*\left( {2 - x_{jkl} - x_{ik - 1l} } \right) \ge C_{i} + s_{ij} + p_{j} \quad \forall i,j,k,l\quad i \ne j, k > 1 $$
(3)

Constraint (2) indicates that the completion time of the first job assigned to any machine should be equal to the sum of the processing time, setup time for the first job and waiting time of job j. Constraint (3) calculates the completion time of jobs apart from the first sequence.

$$ \mathop \sum \limits_{j} x_{jkl} \le 1 \quad \forall k,l $$
(4)
$$ \mathop \sum \limits_{k} \mathop \sum \limits_{l} x_{jkl} = 1 \quad \forall j$$
(5)

Constraints (4) and (5), respectively, ensure that at most one job can be assigned to any sequence in a machine, and each job must be assigned to any sequence in a machine.

$$ b_{jl} \ge x_{jkl} \quad \forall j, k,l $$
(6)

Constraint (6) was formed to ensure that jobs are only assigned to a machine that is available considering technical conditions.

$$ \mathop \sum \limits_{j} x_{jkl} - \mathop \sum \limits_{i} x_{ik - 1l} \le 0\quad \forall k,l,\,\quad k > 1 $$
(7)

Constraint (7) ensures that the jobs are scheduled without skipping any order.

$$ a_{j} \le C_{j} - p_{j} - s_{ij} + M*\left( {2 - x_{jkl} - x_{ik - 1l} } \right)\quad \forall i,j,k,l\quad i \ne j, k > 1 $$
(8)
$$ a_{j} \le C_{j} - p_{j} - h_{j} + M*\left( {1 - x_{jkl} } \right)\quad \forall j,k,l\quad k = 1 $$
(9)

Constraints (8) and (9) determine the starting times of jobs.

There are at most four situations for job j and q that use shared resources in any schedule. These situations are shown in Fig. 1.

Fig. 1
figure 1

Four situations for job j and job q that use shared resources

Full size image

(a) If job q starts earlier than job j and these jobs overlap, \( a_{q} \le a_{j} \) and \( a_{j} \le C_{q} \). Constraints (10) and (11) are for situation 1. If situation 1 occurs, the binary decision variable e1jq is equal to one.

$$ a_{q} \le a_{j} + M*(1 - e1_{jq} ) \qquad \forall j,q,r \quad j < q, \,\,{\text{res}}_{jr} = 1 \,\,{\text{and}}\,\,{\text{res}}_{qr} = 1, q \le n $$
(10)
$$ a_{j} \le C_{q} + M*(1 - e1_{jq} ) \qquad \forall j,q,r \quad j < q, \,\,{\text{res}}_{jr} = 1\,\, {\text{and}}\,\, {\text{res}}_{qr} = 1, q \le n $$
(11)

(b) If job j starts earlier than job q and these jobs overlap, \( a_{j} \le a_{q} \) and \( a_{q} \le C_{j} \). Constraints (12) and (13) are for situation 2. If situation 2 occurs, the binary decision variable e2jq is equal to one.

$$ a_{j} \le a_{q} + M*(1 - e2_{jq} ) \qquad \forall j,q,r j < q, res_{jr} = 1 \,\,\text{and}\,\, res_{qr} = 1, q \le n $$
(12)
$$ a_{q} \le C_{j} + M*\left( {1 - e2_{jq} } \right) \qquad \forall j,q,r\quad j < q, \,\,{\text{res}}_{jr} = 1 \,\,{\text{and}}\,\, {\text{res}}_{qr} = 1, q \le n $$
(13)

(c) If job q is completed before job j starts, \( C_{q} \le a_{j} \). Therefore, these jobs do not overlap. Constraint (14) is for situation 3. If this situation occurs, the binary decision variable e3jq is equal to one.

$$ C_{q} \le a_{j} + M*(1 - e3_{jq} )\quad \forall j,q,r\quad j < q, \,\,{\text{res}}_{jr} = 1 \,\,{\text{and}}\,\, {\text{res}}_{qr} = 1, q \le n $$
(14)

(d) If job j is completed before job q starts,\( C_{j} \le a_{q} \). Therefore, these jobs do not overlap. Constraint (15) is for situation 4. If this situation occurs, the binary decision variable e4jq is equal to one.

$$ C_{j} \le a_{q} + M*(1 - e4_{jq} )\quad \forall j,q,r\quad j < q, \,\,{\text{res}}_{jr} = 1 \,\,{\text{and}}\,\, {\text{res}}_{qr} = 1, q \le n $$
(15)

Constraint (16) ensures that only one situation (1, 2, 3 or 4) can occur for each job couple sharing the same resource.

$$ e1_{jp} + e2_{jq} + e3_{jq} + e4_{jq} = 1\quad \forall j,q,r\,\,\,\,j < q, \,\,{\text{res}}_{jr} = 1 \,\,{\text{and}}\,\, {\text{res}}_{qr} = 1, q \le n $$
(16)

If some resources have copies, it is possible to schedule two jobs requiring the same resource in different machines at the same time. For example, if one resource has one copy, the jobs share this resource and can overlap once. Constraint (17) allows job couples using the same resource to be used at most (fr) times in different machines. The number of overlapping jobs using the same resource is limited to the number of available related resources.

$$ \mathop \sum \limits_{l = 1} \lambda_{jl} \le f_{r} \quad \forall j,r\,\,\,{\text{res}}_{jr} = 1 $$
(17)

To determine overlapping jobs, the model should count how many times job j can overlap with job q that uses resource r in different machines and is provided by Constraints (18)–(21) with the help of decision variable \( \lambda_{jl} \).

$$ 1 + \lambda_{jl} \ge e1_{jq} + \mathop \sum \limits_{k = 1} x_{jkl} \quad \forall j,q, l, \,\,j \ne q $$
(18)
$$ 1 + \lambda_{jl} \ge e1_{jq} + \mathop \sum \limits_{k = 1} x_{qkl} \quad \forall j,q, l\quad j \ne q $$
(19)
$$ 1 + \lambda_{jl} \ge e2_{jq} + \mathop \sum \limits_{k = 1} x_{jkl} \quad \forall j,q, l\quad j \ne q $$
(20)
$$ 1 + \lambda_{jl} \ge e2_{jq} + \mathop \sum \limits_{k = 1} x_{qkl} \quad \forall j,q, l \,\,\,\,j \ne q $$
(21)

Finally, constraints (22)–(26) are the sign constraints of the decision variables:

$$ x_{jkl} \in \left\{ {0,1} \right\}\quad \forall j,k,l $$
(22)
$$ \lambda_{jl} \in \left\{ {0,1} \right\}\quad \forall j,l $$
(23)
$$ e1_{jq} ,e2_{jq} ,e3_{jq} , e4_{jq} \in \left\{ {0,1} \right\}\quad \forall j,q \in N $$
(24)
$$ C_{j} \ge 0\quad \forall j \in N $$
(25)
$$ a_{j} \ge 0\quad \forall j \in N $$
(26)

We called the mathematical model M1. Alternatively, another mixed-integer programming model proposed by Avalos-Rosales et al. (2015) is modified based on overlapping constraints, referred to as M2. The job set N plus a dummy job 0 is denoted by N0 in M2. The processing times and setup times associated with the dummy job are equal to zero. M2 has a new variable yijl, instead of xjkl, in addition to the above defined variables that can be denoted as follows:

$$ y_{ijl} = \left\{ {\begin{array}{*{20}l} {1,} & {{\text{if}}\,\,{\text{job}}\,i\,\,{\text{is}}\,\,{\text{scheduled}}\,\,{\text{before}}\,\,{\text{job}}\,\,j\,{\text{on}}\,\,{\text{machine}}\,\,l ,} \\ {0,} & {{\text{otherwise}}.} \\ \end{array} } \right. $$

The constraints of M2 with the objective function (1) can be stated as follows:

$$ \mathop \sum \limits_{l \in L} \mathop \sum \limits_{{i \in N_{0} ,i \ne j}} y_{ijl} = 1\quad \forall j \in N $$
(27)
$$ \mathop \sum \limits_{l \in L} \mathop \sum \limits_{{j \in N_{0} ,j \ne i}} y_{ijl} = 1\quad \forall i \in N $$
(28)

Constraints (27) and (28), respectively, ensure that each job has exactly one predecessor and one successor.

$$ \mathop \sum \limits_{{j \in N_{0} ,i \ne j}} y_{ijl} - \mathop \sum \limits_{{q \in N_{0} ,q \ne i}} y_{qil} = 1\quad \forall i \in N, \quad \forall l \in L $$
(29)

Constraint (29) establishes that each job in a machine should have a predecessor and a successor in the same machine.

$$ \mathop \sum \limits_{j \in N} y_{0jl} \le 1 \quad \forall l \in L $$
(30)

Constraint (30) guarantees that at most one job can be assigned to the first sequence in a machine.

$$ C_{j} - C_{i} + M*\left( {1 - y_{ijl} } \right) \ge s_{ij} + p_{j} + wt_{j} \quad \forall i \in N_{0} , \forall j \in N, i \ne j $$
(31)

The completion time of jobs calculated by Constraints (31) and (32) are formulated for machine eligibility restrictions.

$$ b_{jl} \ge \mathop \sum \limits_{{i \in N_{0} }} y_{ijl} \quad \forall j \in N_{0} , \forall l \in L $$
(32)

Constraints (33) and (34) provide the calculation of starting times:

$$ a_{j} \ge C_{i} + wt_{j} - M*\left( {1 - y_{ijl} } \right) \quad \forall i,j \in N_{0} , l \in L \quad i \ne j, j > n $$
(33)
$$ a_{j} \le C_{i} + wt_{j} + M*\left( {1 - y_{ijl} } \right) \quad \forall i,j \in N_{0} , l \in L\quad i \ne j, j > n $$
(34)

The completion time of a dummy job is equal to zero and is explained by Constraint (35).

$$ C_{0} = 0 $$
(35)

The equation numbers of overlapping constraints for M2 are (10)–(21). Constraints (23)–(26) and (36) are for sign constraints.

$$ y_{ijl} \in \left\{ {0,1} \right\}\quad \forall i,j,l $$
(36)

M1 and M2 were tested using a small example:

Example There are five jobs, two machines and two resources. The processing times and setup times of job j are first in the following sequence: \( p_{j} = \left\{ {20,30,10,20,15} \right\} \), \( h_{j} = \left\{ {10,20,15,10,5} \right\} \), where \( j = 1, \ldots ,5. \) Sequence-dependent setup times between the two jobs are shown in Table 1.

Table 1 Sequence-dependent setup times between job i and job j (sij)
Full size table

Machine eligibility restrictions are given as follows: job 1 and job 3 can only be processed on machine 1. Job 2, job 4 and job 5 can only be processed on machine 2. resjr denotes the type of resource required by job j, and this parameter is given in Table 2, and the amount of resource r (fr) is also given in Table 3. The weights of job j (wj) are given as follows: \( w_{j} = \left\{ {9,2,6,5,7} \right\} \)

Table 2 The type of resource required by the jobs (resjr)
Full size table
Table 3 The amount of resource r (fr)
Full size table

The example was solved using M1 and M2 with the GAMS/Cplex solver. An optimal solution was found in 28 and 12 s with M1 and M2, respectively. The objective value of the optimum schedule was 2230. The Gantt Scheme of the obtained results is shown in Fig. 2.

Fig. 2
figure 2

Gantt scheme of example

Full size image

In Fig. 2, the jobs using the same resources are shown in the same color. As seen in the figure, jobs 1 and 5 could not be produced at the same time because resource 1 had no copies. However, two of jobs 2, 3 and 4 could be scheduled at the same time since resource 2 had two copies.

3 Proposed matheuristics

Matheuristics are model-based (meta)heuristics. These methods combine the advantages of both exact methods and (meta)heuristics. Therefore, researchers have recently shown an increased interest in matheuristics. A number of studies have used matheuristics in scheduling problems. For example, Billaut et al. (2015) handled a scheduling problem in which jobs consumed a perishable resource stored in vials. The problem was modeled as a single machine scheduling problem with additional duration and consumption constraints. They proposed a two-step approach that consisted of a recovering beam search algorithm and a matheuristic algorithm. Guimaraes et al. (2013) considered a single machine capacitated lot sizing and scheduling problem with sequence-dependent setup times and costs. They presented a MIP-based heuristic (matheuristic) model for solving this problem. Finally, Singha et al. (2012) focused sensor coverage scheduling in wireless sensor networks subject to Q-coverage constraints. The objective of the problem was to maximize the network lifetime. A matheuristic algorithm that included a GA and a linear programming model was developed.

The IPMS–SMS instances, especially if they are large-scale problems, cannot be solved easily due to their NP-hard nature. An efficient heuristic search would be useful to address such a problem. In this study, we developed a special version of a model-based GA to solve the IPMS–SMS. The proposed matheuristic algorithms have a different structure from a classic GA. In a classic GA, solutions are coded as chromosomes, and this representation contains all the values of the decision variables of the considered problem, so fitness values of the chromosomes can be calculated using these values. However, solutions may be very far from the optimum solution. In the proposed GA, a chromosome contains only the values of the decision variable xjkl. After determining the value of the decision variables xjkl using the GA, determining the values of the remaining decision variables is still a decision problem. In this study, a subproblem is solved by GAMS/Cplex to calculate the fitness value. The subproblem (M3) is very similar to M1, but a new decision variable (wtj) is defined for calculating the waiting time of job j in M3. In addition, xjkl are parameters and not decision variables, and M1 is tightened using the xjkl values. Therefore, we can find optimal solutions of the fitness value when subproblem M3 is solved. Since the fitness value is directly affected, better solutions can be obtained than with a classical GA with fewer population and generation sizes. The subproblem (M3) is given below:

$$ C_{j} = h_{j} + p_{j} + wt_{j} \quad \forall j,k,l \,\,\,k = 1\quad \,{\text{and}}\,\,\,x_{jkl} = 1 $$
(37)
$$ C_{j} = C_{i} + p_{j} + s_{ij} + wt_{j} \quad \forall i,\,j,\,k,\,l\,i \ne j,\,\, k > 1,\,\,\,\,x_{jkl} = 1 \,{\text{and }}\,\,x_{jk - 1l} = 1 $$
(38)
$$ a_{j} = C_{i} + wt_{j} \quad \forall i,j,k,l\,\,\,\,\,i \ne j, \,\,\,\,k > 1\,\,\,x_{jkl} = 1\,\, {\text{and}}\,\,\, x_{jk - 1l} = 1 $$
(39)
$$ a_{j} = wt_{j} \quad \forall j,k,l\,\,\,\,\,k = 1\,\,{\text{and}}\quad x_{jkl} = 1 $$
(40)

(10)–(21)

(23)–(26)

xjkl values contain information about jobs and their sequence in machines by means of chromosome values. To determine the starting time, completion time and waiting time of jobs, M3 is solved. Constraints (37) and (38) calculate the completion time of jobs. Constraints (39) and (40) determine the starting times of jobs.

In the proposed algorithm (MA), the GA and the subproblem (M3) work cooperatively. The xjkl values obtained by the GA transform the parameters of M3, and the objective function value of M3 transforms to the GA as the fitness value of the related chromosome. This relationship between the GA and M3 is shown in Fig. 3.

Fig. 3
figure 3

The relationship between the GA and subproblem-M3

Full size image

3.1 Representation

The chromosome representation of the proposed algorithm is a 2xn-bit integer matrix. All the genes in the first row of the chromosome have values between 1 and m, and the genes in the second row of the chromosome have values between 0 and 1. The sequence of the genes shows the job index for both rows. The first row of the matrix represents the machines to which the jobs are assigned. The second row of the matrix represents the job sequences. For example, a sample solution for the 6-job, 3-machine problem is given as the following bit matrix:

3

1

2

1

2

3

0.2

0.5

0.6

0.3

0.1

0.5

This means that jobs 2 and 4 are selected for machine one, jobs 3 and 5 are selected for machine two and jobs 1 and 6 are selected for machine three. The sequence of the jobs is identified according to the second row of the chromosome. Determining the initial job sequences, organizing the job sequences and assigning the x(jkl) value procedures are given in Sect. 3.2.

GA starts with the encoding of a chromosome and it is followed by generating an initial population. In the proposed algorithm, the initial population is constructed in three ways: (1) M1 assignment model (M1-A), (2) M2 assignment model (M2-A), (3) Random assignment.

  1. (1)

    M1 assignment model (M1-A) is a reduced version of M1 that considers Constraints (2)–(7) and sign constraints (22) and (25) to minimize total weighted completion time. M1-A performs in 1500 s in GAMS/Cplex, and the first chromosome of the initial population is obtained.

  2. (2)

    The M2 assignment model (M2-A) is a reduced version of M2 that considers Constraints (27)–(32) and (35) and sign constraints (25) and (36) to minimize the total weighted completion time. M2-A also performs in 1500 s in GAMS/Cplex, and the second chromosome of the initial population is obtained.

  3. (3)

    The rest of the initial population is determined by a purely random assignment of jobs considering machine eligibility restrictions. The other chromosomes are constructed by generating random numbers in the range [1, m] for each of the genes in the first row and in the range [0, 1] for each of the genes in the second row of chromosomes. Machine eligibility restrictions are considered when generating the first row. Therefore, the chromosomes of the initial population represent feasible solutions. The pseudo-code of the initial population generation procedure for random assignment is given below:

    figure a

where kr: chromosome, j: job, l: machine, rnumber: a random number, gen(kr,j): jth gene value of chromosome kr, rseq(kr,j): a random number for sequence of job j in chromosome kr

3.2 Fitness function

The fitness value of the chromosome is equal to the total weighted completion time. The genetic algorithm determines the value of the decision variable “xjkl”, which gives information about a particular job’s assignment, its machines and its order. After determining the value of the decision variables xjkl using the GA, determining the values of the remaining decision variables is still difficult and remains a decision problem. In this study, we solve a subproblem (M3) to calculate the fitness value. Based on the GA’s assignment, the M3 model determines the starting time, waiting time and completion time of jobs under all constraints. The pseudo-code used for calculating the fitness value consists of three parts. First, one determines the jobs that are assigned to the same machines. After that, jobs are sorted in increasing order of random numbers in the second part. The last part is for assignment for the value of parameter x and calculating the fitness value. The entire pseudo-code is given below:

* Determining the initial job sequences

figure b

* Organizing the job sequences

figure c

* Assigning the x(j,k,l) value and calculating the fitness value

figure d

where seq(kr,j): sequence of job j in chromosome kr, Fit(kr): fitness function value of chromosome kr,

3.3 Genetic operators

A classic GA is composed of three operators: reproduction, crossover and mutation. The reproduction operator allows individual chromosomes to be copied for possible inclusion in the next generation. The chance that a chromosome will be copied is based on the chromosome’s fitness value, calculated from a fitness function. We used a 2-tournament selection method as a reproduction operator. In 2-tournament selection, two chromosomes are randomly selected. The fitness values of the chromosomes are compared. The chromosome with a better fitness value is selected for the next generation. This continues until the number of selected chromosomes is equal to the population size. Crossover enables the algorithm to extract the best genes from different individuals and recombine them into potentially superior children. The proposed GA has a two-point crossover operator. A sample crossover is given in Fig. 4. In the example, a chromosome of Parent 1 and a chromosome of Parent 2 are aligned. Crossing points are selected randomly. It shows the borders of the genes that are given in black boxes. Child 1 gets the genes of Parent 1 except for the crossing point. The remaining genes of Child 1 are copied from the chromosome of Parent 2. The genes in the crossing point of Parent 1 are copied to Child 2. Other genes in Child 2 are the same as in Parent 2. As shown in Fig. 4, only genes in the crossing point of each chromosome are changed, so eligibility constraints are still satisfied.

Fig. 4
figure 4

Crossover

Full size image

Reproduction and crossover alone can obviously generate a staggering number of differing chromosomes. However, depending on the initial population chosen, there may not be a sufficient variety of chromosomes to ensure the GA searches the entire problem space, or the GA may find itself converging on chromosomes that are not quite close enough to the optimum it seeks due to a bad initial population. Introducing a mutation operator into the GA may prevent some of these problems. In the proposed algorithm, a random number is generated for all the genes. If the random number is smaller than the mutation rate, the value of the gene is generated according to the initial population generation procedure so that machine eligibility restrictions are considered. The value of the gene is protected if the random number is greater than the mutation rate. A sample mutation is given in Fig. 5. In this example, the mutation rate is equal to 0.25. Random numbers of the first and fourth genes are smaller than the mutation rate. Therefore, these genes are regenerated according to the initial population procedure, and Chromosome 2 is obtained.

Fig. 5
figure 5

Mutation

Full size image

Since elitism selection improves the efficiency of a GA considerably, as it prevents a loss of the best results, it is used in the developed GA. In this study, two types of termination conditions are used together. The first condition checks whether the algorithm has run a fixed number (nf) of generations. The other stops the algorithm if the total solution time reaches ‘nt’.

4 Computational results

To test the performance of the proposed MIP models, randomly generated instances were used. Since the identical parallel machine scheduling problem with sequence-dependent setup times, machine eligibility restrictions and multiple copies of shared resources has been defined firstly in this paper, we could not find test instances from the scheduling literature. Therefore, instances were generated randomly. The proposed MIP formulations and the matheuristic algorithm were coded in GAMS 24.0.2 and were run using the Cplex solver embedded in GAMS on a 2.8-GHz Intel Core i7 with 4 GB RAM. The characteristics of the test problems and the obtained results of the GAMS/Cplex solver and the matheuristic algorithm are given in the following subsections.

4.1 Test problems

In the identical parallel machine scheduling literature, generally the number of jobs (n) is approximately eight for small-sized test problems (Gacias et al. 2010; Chen and Chen 2009), approximately forty for medium-sized test problems (Edis and Oguz 2012; Gacias et al. 2010; Nessah et al. 2007) and one hundred for large-sized test problems (Montoya-Torres et al. 2009; Gacias et al. 2010; Tahar et al. 2006). In this study, we generated instances with n = 8, n = 40 and n = 100. Other parameters by generating instances and their levels are given separately for problems n = 8, n = 40 and n = 100 in Table 4.

Table 4 Problem parameters with their levels
Full size table

As shown in Table 4, the number of machines (m) is two or three for instances with n = 8, two or six for instances with n = 40 and two and eight for instances with n = 100. In the literature, similar m values are used (Montoya-Torres et al. 2009; Lin et al. 2011; Tahar et al. 2006). The number of resource types (g) is two or five for instances with n = 8, four or twenty for instances with n = 40 and eight or fifty for instances with n = 100. The processing times (pj) and the setup times for first jobs (hj) are drawn from a uniform distribution on [1,100] rounded to the nearest integer. Sequence-dependent setup times (sij) are drawn from a uniform distribution on [1,10], if job i and job j use the same resource, and on [1,100] if they use different resources. If job j can be processed on machine l, bjl is equal to 1. rb is the rate of bjl parameters other than zero, and we fixed this rate at 0, 25 and 1. If the type of resource r required by job j, resjr is equal to 1, gres is an indicator used to show generation type. If it is (1), resjr is generated randomly. If it is (2), resjr is generated as one resource dense. The amount of resource r (fr) is generated with a uniform distribution in the range [1,2]. By using these levels of parameters, 16 problem types occur, and we generated three instances for each type using Excel VBA.

All instances of IPMS with SMS are available on the web site (http://endustri.ogu.edu.tr/Personel/Akademik_personel/Tugba_Sarac_Test_Instances/IPMS_with_SMS_instances.rar)http://endustri.ogu.edu.tr/Personel/Akademik_personel/Tugba_Sarac_Test_Instances/TOP_AKYOLOZER_SARAC_Instances.rar).

4.2 Test results of the GAMS/Cplex

Each of the generated test problems with n = 8, n = 40 and n = 100 was solved by means of the proposed models (M1 and M2). The running time of the Cplex solver of GAMS was limited to 7200 s for all the tests. To evaluate the relative performance of the model and matheuristic algorithm, we utilized two types of performance measures, namely relative percentage deviation (RPD1, RPD2) and GAMS relative gap (GAP).

  • RPD1 is equal to the difference between solutions of M1 and M2. RPD2 is defined as the difference between the best solution of the models and the solution of the matheuristic algorithm for each instance. RPD1 and RPD2 are calculated by Constraints (41) and (42), as follows:

$$ {\text{RPD}}1 \left( \% \right) = \frac{{Z_{\text{M1}} - Z_{\text{M2}} }}{{Z_{\text{M2}} }} $$
(41)
$$ {\text{RPD}}2 (\% ) = \frac{{Z_{{\text{MA}}{-}{\text{Min}}} - {\text{Min}}\left( {Z_{\text{M1}} ,Z_{\text{M2}} } \right)}}{{Z_{{\text{MA}}{-}{\text{Min}}} }}, $$
(42)

where ZMA-Min denotes the minimum objection function value of the matheuristic algorithm, and ZM1 and ZM2 denote the objection function values for M1 and M2, respectively.

  • GAP is obtained by GAMS/Cplex after solving mathematical models M1 and M2.

The results of small-sized (n = 8) problems are presented in Table 5. In this table, the first four columns summarize the properties of instances such as instance number (no), number of resources (g), rate of bjl parameters other than zero (rb) and generation type of resjr (gres). The fifth and sixth columns show the obtained objective value and solution time in seconds using the GAMS/Cplex solver with M1. The last two columns represent the results of the M2 model for small size instances.

Table 5 GAMS/Cplex results for small instances with n=8
Full size table

As we can see from Table 5, M1 and M2 are capable of solving to optimality almost all small instances in reasonable time. For only one instance (9-2), the running time limit is exceeded in M2 before reporting the obtained best integer solution is optimal. It can be clearly observed that M2 is remarkably more efficient than M1 with regard to running time. Differences between the running times of M1 and M2 are distinctly decreased with increases in the number of machines.

Test results for medium size instances (n = 40) obtained using M1 and M2 are summarized in Table 6. M1 could obtain feasible solutions for 80% of the medium-size instances in 7200 s, and the GAP value of all these solutions is 0.99. However, M2 could solve feasible solutions for only 30 percent of the instances, and the average GAP value is 0.72. This implies that M1 indicated a significantly poor performance compared to M2, although M1 has more feasible solutions.

Table 6 GAMS/Cplex results for medium instances with n = 40
Full size table

Finally, feasible solutions could not be found in 7200 s using M1 and M2 for all large instances except for one instance (8-1) with M1.

4.3 Test results of the proposed matheuristic algorithm

First, a small-size (n = 8) instance (no: 6-2) was solved using the matheuristic algorithm with the following parameters: population size is 30, crossover rate is 0.7, mutation rate is 0.2 and the values of the termination parameters are nf  =  500 and nt  =  7200. The obtained convergence graph of the matheuristic algorithm is shown in Fig. 6. As shown in Fig. 6, the matheuristic algorithm can reach the optimal objective value (6785) of the instance.

Fig. 6
figure 6

Convergence graph of the matheuristic algorithm

Full size image

The parameter values of any meta-heuristic algorithm directly affect their performance. A full factorial experimental design was used to determine the proper parameter values of the matheuristic algorithm for each problem size. Factors and their levels are given in Table 7.

Table 7 Factors and their levels
Full size table

Population size, crossover rate and mutation rate are critical factors according to analysis of variance for small instances. Related main effect plots are given in Fig. 7. The parameters of the small instances were as follows: the population size was 30, the crossover rate was 0.7 and the mutation rate was 0.2.

Fig. 7
figure 7

Main effect plots for small problems

Full size image

Interaction between the population size and mutation rate is critical according to analysis of variance for medium instances, and the mutation rate is a critical factor according to analysis of variance for large instances. Related interaction and main effect plots are given in Figs. 8 and 9, respectively. The parameters of the medium and large instances were as follows: the population size was 10, the crossover rate was 0.6, and the mutation rate was 0.1.

Fig. 8
figure 8

Interaction plot for medium problems

Full size image
Fig. 9
figure 9

Main effect plots for large problems

Full size image

The values of the termination parameters were nf = 100, the solution time limit (nt) was 7200 s for all instances, and they were carried out in three runs.

The matheuristic algorithm results of the small instances for different values of m (2, 3) are presented in Table 8. In this table, the first column shows the instance number (no). The second column shows the average solution time in seconds of three runs for each problem type. The last column describes the RPD2 value to demonstrate the success of the matheuristic algorithm.

Table 8 Matheuristic algorithm results for small instances with n = 8
Full size table

In Table 5, the GAMS/Cplex solver provides the optimal solutions of all small instances. The matheuristic algorithm obtained the optimal solution for approximately 60 percent of the small instances. As shown in Table 8, RPD2 values completely depend on the number of machines and the number of resources. With the large number of machines (m = 3) and small number of resources (g = 2) for small instances (which represent problems between 9-1 and 12-3), RPD2 has peak percentage values (approximately 0.13). As expected, the RPD2 values of small instances with g = 5 (which represent problems between (5-1 and 8-3) and (13-1 and 16-3)) are extremely small and approximately zero.

In Table 9, the results of the matheuristic algorithm for medium instances are presented. This table is structured in a similar way as Table 8. As Table 9 shows, RPD2 values of eight medium instances with m = 2 (1-2, 2-2, (3-1)-(4-3)) could not be calculated since a feasible solution could not be provided by M1 or M2. RPD2 has a positive value for four instances (%10) since the mathematical models exhibit good performance. However, the proposed matheuristic algorithm has better results with significantly high RPD2 values for the remaining instances. The average RPD2 value is 0.7, and the widest RPD2 value that is larger than 1 is recorded for instance (1-1).

Table 9 Matheuristic Algorithm results for medium instances with n=40
Full size table

In Table 10, the results of the matheuristic algorithm for large instances are given. In this table, the first column shows the number of machines (m). The second column gives the number of large instances for each machine number. The following two columns show the number of instances that are solved in 7200 s by mathematical models and matheuristic algorithms, respectively. The last two columns describe the averages of the minimum objective values of the three runs and solution times obtained by the proposed matheuristic algorithm. The GAMS/Cplex solver could obtain a feasible solution in 7200 s only for instance (8-1). The RPD2 value of regarding instance is 0.32. The proposed matheuristic algorithm provides feasible solutions for all large instances in a reasonable time. However, instances with m = 8 reach running time limits before the number of generations could not be complete, and the average of solution times is equal to the time limit (7200 s).

Table 10 Matheuristic algorithm results for large instances with n = 100
Full size table

5 Conclusion

In this study, an identical parallel machine scheduling problem with sequence-dependent setup times, machine eligibility restrictions and multiple copies of shared resources was analyzed. To the best of our knowledge, this problem has not been studied before. A MIP model is proposed. However, to compare the performance of mathematical model M1, a modification of the makespan model that is presented in Avalos-Rosales et al. (2015) is presented and is called M2. To overcome large instances, a matheuristic algorithm is developed. Initial solutions of the proposed algorithm are generated by reduced versions of M1 and M2. We executed computational experiments based on randomly generated instances with small, medium and large sizes. Optimal schedules were obtained for almost all small problems within a reasonable time for M1 and M2. However, M2 exhibits significantly improved performance in the manner of solution time for small problems. In medium instances, although M2 gives a rather high-quality solution, M1 offers more feasible solutions. Furthermore, the RPD2 values are quite wide, which indicates that MA shows clearly good performance. Finally, feasible solutions are obtained for all large instances in a reasonable time with the proposed matheuristic algorithm.

For future research, this problem can be considered multiobjective. For example, total tardiness is a significant objective for this kind of problem. Furthermore, the performance of other meta-heuristic algorithms, such as tabu search and simulated annealing, could be investigated to solve this problem.