# Two Parallel-Machine Scheduling Problems with Function Constraint

Authors: Chia-Lun Hsu; Jan-Ray Liao
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

The objective of this paper is to minimize both the makespan and the total completion time. Since parallel-machine scheduling which contains the function constraint problem has been a new issue, this paper explored two parallel-machine scheduling problems with function constraint, which refers to the situation that the two machines have a same function but one of the machines has another. We pointed out that the function constraint occurs not only in the manufacturing system but also in the service system. For the makespan problem, we demonstrated that it is NP-hard in the ordinary sense. In addition, we presented a polynomial time heuristic for this problem and have proved its worst-case ratio is not greater than 5/4. Furthermore, we simulated the performance of the algorithm through computational testing. The overall mean percent error of the heuristic is 0.0565%. The results revealed that the proposed algorithm is quite efficient. For the total completion time problem, we have proved that it can be solved inOn4 time.


---

## Body

## 1. Introduction

The scheduling problem studied in this paper was motivated by the manufacturing of the metal processing industry. In the traditional manufacturing, a lathe machine and a milling machine have different functions. Generally speaking, the lathe machine is a tool that rotates a workpiece about an axis of rotation to perform various operations such as cutting, deformation, knurling sanding, and turning. The milling machine is used to cut the plane, while the shape of the forming surface, the spiral groove, or the tooth shape of the gear is milled with a special-shaped milling cutter. During milling, the workpiece is mounted on a table or an indexing head attachment, and the milling cutter performs a cutting motion, supplemented by a table for feeding motion. And now, a 5-axis machining center for milling and turning has all the functions of lathe machine and milling machine. As the company's performance grows rapidly, companies must purchase machines to meet customer needs. While newly purchased machines tend to have more function than older machines, functional alternatives occur between machines. We named this phenomenon as function constraint (e.g., lathe machine versus 5-axis machining centers for milling and turning). The function constraint occurs not only in the manufacturing system but also in the service system. In the service system, the parallel-machine is composed by the employees. The senior staff, the junior employees, and the new employees all have the ability to limit and replace.Parallel machine in a production environment can be divided into three categories according to the nature of the machine: identical, uniform, and unrelated parallel machines. For decades, the parallel-machine production scheduling problem has been extensively studied under various classical scheduling performance measurement criteria. The makespan and total completion time are the two best important performance measurement criteria. The makespan is also called the maximum completion time or the completion time of the last workpiece on the last machine. The makespan is usually used to measure the utilization of machinery and equipment. If one shortens the makespan and the machine utilization and production efficiency is improved, more flexible time can be reserved to prevent the sudden occurrence of the production line. The completion time refers to the time spent in the system from the time of the workpiece that arrives at the site to its completion, and the total completion time is the sum of the completion time of all the workpieces. Therefore, the total completion time is expected to be minimized. That is, the in-process inventory of the factory is expected to be minimized to reduce the cost of inventory.Chung et al. [1] explored a two identical parallel-machine scheduling problem with molds constraints. Their objective is to minimize the makespan. For the problem is NP-hard, they give three heuristics and analyze each heuristic has a worst-case performance ratio of 3/2. Computational results revealed that heuristics are efficient even for the large-sized problem. Xu and Yang [2] studied a two parallel-machine scheduling with a periodic availability constraint. Their objective is to minimize the makespan. Because the problem is NP-hard, they present a mathematical programming model to solve it and, next, compare the performance of the longest processing time first (LPT) algorithm with the list scheduling (LS) via computational experiments. Most of the results showed that the LPT is better than the LS. Xu et al. [3] examined a two parallel machine scheduling problem to minimize the makespan. The problem is known as NP-hard. They applied the branch-and-bound method to solve the small-sized problem and presented a Tabu search algorithm for the large-sized problem. Ji and Cheng [4] presented a fully polynomial-time approximation scheme for parallel-machine scheduling under a grade of service provision to minimize makespan consideration. Lee et al. [5] addressed a makespan minimization scheduling problem on identical parallel-machine. They applied the simulated annealing method, and several heuristic algorithms have been proposed to tackle the problem. Computational results demonstrated that the simulated annealing method is efficient and better than the existing methods. Yin et al. [6] explored parallel-machine scheduling of deteriorating jobs with potential machine disruptions. The authors examined two cases of machine disruption (i.e., performing maintenance immediately on the disrupted machine when a disruption occurred and not performing machine maintenance). The nature of the jobs has two types: nonresumable and resumable. They determined the computational complexity status of various cases of the total completion time minimization problem and provided pseudopolynomial-time solution algorithms and fully polynomial-time approximation schemes for them.Zhao et al. [7] explored a two parallel-machine scheduling problem where one machine is not available in a specified time period. The unavailable time period is fixed and known in advance. They proposed a fully polynomial-time approximation scheme for the total weighted completion time minimization problem and generalized the results to the case with m parallel machine. Kuo and Yang [8] studied parallel-machine scheduling with time-dependent processing time. For the total completion time and the total load problems, they showed that the two problems are polynomially solvable. Gerstl and Mosheiov [9] proposed a general position-dependent processing time model. They considered scheduling problems which combine the option of job rejection and the model on parallel machine. Their objectives are total flow-time and total load. They proved that both problems can be solved in polynomial time in the number of jobs. Huang and Wang [10] stressed parallel-machine scheduling problems with deteriorating jobs. They showed that the total absolute differences in completion time and the total absolute differences in waiting time minimization problems can be solved in polynomial time.Wang and Wang [11] studied a three-machine permutation flow shop scheduling problem with time-dependent processing times. The objective is to find a sequence that minimizes the makespan. Several dominance properties and a lower bound are derived to speed up the elimination process of a branch-and-bound algorithm. Moreover, two heuristic algorithms are proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational results show that the heuristic algorithm M-NEH performs effectively and efficiently.For more information, the reader may refer to the concise surveys on this topic by Cheng and Sin [12], Mokotoff [13], Pfund et al. [14], Kravchenko and Werner [15], Kaabi and Harrath [16], and Wang and Li [17].Parallel-machine scheduling combines the function constraint problem is a new issue. Therefore, this paper explored two parallel-machine scheduling problems with function constraint. The objectives are to minimize the makespan and the total completion time.The rest of the paper is organized as follows. In Section2, we introduced the notation and formally formulated our problems. In Section 3, we demonstrated the computational complexity status and presented a heuristic algorithm, worst-case ratio, and computational experiments for the makespan minimization problem. In Section 4, we formulated the total completion time minimization problem as an assignment. In the last section, we concluded the paper and suggested issues for the future research.


## 2. Problem Formulation

There aren jobs in the set N=J1,J2,...,Jn1,Jn1+1,...,Jn. Assume set N consists of two classes of job that are the first class jobs and the second class jobs. Let n1 and n2 denote the number of jobs of the first class and the second class, respectively. Let S1 and S2 denote the set of the jobs of the first class and the second class, respectively. That is, N=S1∪S2, where S1=J1,J2,...,Jn1 and S2=Jn1+1,...,Jn. Let pj denote the processing time of Jj (j=1,2,...,n). Assume there are two parallel machines Mi (i=1,2), where M1 can process the first class jobs only and M2 can process both of the first class jobs and the second class jobs. Some common assumptions are as follows: (1) all jobs are non-preemptive and available for processing at time zero; (2) each machine can handle at most one job at a time and cannot stand idle until the last job assigned to it has finished processing; and (3) each job can be processed on at most one machine at a time. The objectives are to minimize the makespan and the total completion time. We used “fc” to denote the function constraint relations between the two machines. Following the common scheduling notation, the problems can be described as P2fcCmax and P2fcTC, respectively.


## 3. Minimization of the Makespan

In this section, we confirmed the complexity and presented the worst-case bound forP2fcCmax. First, we excluded the case of the sum of processing time in the second class jobs is larger than the sum of processing time in the first class jobs because the first class jobs processed on M1 and the second class jobs processed on M2 are optimal for the abovementioned case. Second, we analyze the complexity of the problem P2fcCmax. Third, we presented a heuristic approach and analyze the worst-case bound of the algorithm. Finally, a computational experiment was conducted to evaluate the performance of the proposed algorithm.


### 3.1. The Heuristic and Worst-Case Bound

The special case of all the jobs belongs to the first class,n1=n, and then the problem P2fcCmax becomes the classical problem P2Cmax. It is known in advance that P2Cmax is NP-hard in the ordinary sense [18]. Therefore, the following theorem holds.Theorem 1.
Scheduling problemP2fcCmax is NP-hard in the ordinary sense.
A simple heuristic approach is described in Algorithm1.
A simple sort can be done inOnlogn (e.g., heap sorting). Hence, the complexity of Step 1 is Onlogn. The complexity of Step 2 is On. Overall, the complexity of the algorithm is Onlogn.
A straightforward result is given as follows.Algorithm 1: The longest processing time first (LPT) approach.
Step 1. Arrange the first class jobs in nonincreasing order, without loss of generality, and assume the LPT sequence remainsJ1,J2,...,Jn1.Step 2. AssignJn1+1,Jn1+2,...,Jn to the M2. After that, whenever a machine is freed, the longest job among those not yet processed in the first class is put on the machine.Lemma 1.
For the problemP2fcCmax, the following holds:(1)
Cmax∗≥∑j=n1+1npj, where Cmax∗ denotes the makespan of the optimal schedule(2)
Cmax∗≥∑j=1n1pj+∑j=n1+1npj/2=LB, where LB denotes the lower bound of the problemTheorem 2.
For the problemP2fcCmax, CmaxLPT≤5Cmax∗/4.Proof.
AssumeJk is the last processed job based on the LPT approach. If Jk∈S2, then CmaxLPT=Cmax∗. Therefore, the following proof processes are under the assumption of Jk∈S1.
Ifk=1, then CmaxLPT=Cmax∗.
For the case ofk≥2, assume sk denotes the starting time of Jk. Since there is no idle time on the machines prior to the time sk,(1)sk≤∑j=1k−1pj+∑j=n1+1npj2=∑j=1kpj+∑j=n1+1npj−pk2≤∑j=1n1pj+∑j=n1+1npj−pk2≤Cmax∗−pk2.
Consider the following two cases:pk≤Cmax∗/2 and pk>Cmax∗/2.
Whenpk≤Cmax∗/2, we have(2)CmaxLPT=sk+pk≤Cmax∗−pk2+pk=Cmax∗+pk2≤Cmax∗+Cmax∗4=5Cmax∗4.
Whenpk>Cmax∗/2, based on optimal consideration, we have ∑j=n1+1npj≤Cmax∗/2 and each machine cannot arrange two jobs that belong to S1 and whose job’s index is less or equal to k. Therefore, Jk is the only job that belongs to S1 and being processed on M2. That is, CmaxLPT=pk+∑j=n1npj. Within the optimal sequence, Jk is the only job that belongs to S1 and can be processed on M2. We have Cmax∗≥CmaxLPT. Hence, Cmax∗=CmaxLPT.


### 3.2. The Computational Experiments

Although the worst case above seems quite good from the theoretical aspects, 25% errors cannot be accepted from the application dimensions. Therefore, some computational experiments were conducted to evaluate the performance of the LPT approach. The LPT approach was coded in Visual BASIC 6.0 and implemented on a personal computer with Intel corei7 16G CPU. Some test problems for each environment were randomly generated, the details of which are as follows:(1)
n is equal to 50, 100, 150, 200, 250, 300, 500, and 1000(2)
n1 is uniformly distributed over [1, n]. n2=n−n1(3)
pi is uniformly distributed over [1, 50], [1, 100], [1, 200], [1, 500], and [1, 1000]A ratio ofCmaxLPT−LB×100/LB is used as an index to evaluate the performance of the LPT approach, where CmaxLPT is the solution found by the LPT approach and LB is the solution found by lower bound. The ratio is computed for 300 test problems in each problem size; hence, 12000 (300 × 8 × 5) test problems are generated for the proposed problem P2fcCmax. The computational results are shown in Table 1. The results revealed that the mean percentage errors of the LPT approach are 0.0214, 0.0397, 0.0560, 0.0741, and 0.0905 with five different processing time distribution periods, respectively. From Table 1, we found that the larger the problem the smaller the error percentages and the wider the processing time range the larger the error percentages. The overall mean percent error of the LPT approach is 0.0565%.Table 1
Computational results of the LPT approach with five different processing time distribution periods.
npiU (1, 50)U (1, 100)U (1, 200)U (1, 500)U (1, 1000)Average500.09710.18840.28170.37140.45760.27921000.02700.04920.07150.09390.11670.07161500.01560.02640.03720.04830.05800.03712000.01050.01740.02360.02950.03500.02322500.00810.01320.01750.02110.02470.01693000.00660.01070.01370.01630.01890.01325000.00400.00590.00710.00800.00890.006810000.00220.00330.00380.00410.00430.0035Average0.02140.03970.05700.07410.09050.0565


## 3.1. The Heuristic and Worst-Case Bound

The special case of all the jobs belongs to the first class,n1=n, and then the problem P2fcCmax becomes the classical problem P2Cmax. It is known in advance that P2Cmax is NP-hard in the ordinary sense [18]. Therefore, the following theorem holds.Theorem 1.
Scheduling problemP2fcCmax is NP-hard in the ordinary sense.
A simple heuristic approach is described in Algorithm1.
A simple sort can be done inOnlogn (e.g., heap sorting). Hence, the complexity of Step 1 is Onlogn. The complexity of Step 2 is On. Overall, the complexity of the algorithm is Onlogn.
A straightforward result is given as follows.Algorithm 1: The longest processing time first (LPT) approach.
Step 1. Arrange the first class jobs in nonincreasing order, without loss of generality, and assume the LPT sequence remainsJ1,J2,...,Jn1.Step 2. AssignJn1+1,Jn1+2,...,Jn to the M2. After that, whenever a machine is freed, the longest job among those not yet processed in the first class is put on the machine.Lemma 1.
For the problemP2fcCmax, the following holds:(1)
Cmax∗≥∑j=n1+1npj, where Cmax∗ denotes the makespan of the optimal schedule(2)
Cmax∗≥∑j=1n1pj+∑j=n1+1npj/2=LB, where LB denotes the lower bound of the problemTheorem 2.
For the problemP2fcCmax, CmaxLPT≤5Cmax∗/4.Proof.
AssumeJk is the last processed job based on the LPT approach. If Jk∈S2, then CmaxLPT=Cmax∗. Therefore, the following proof processes are under the assumption of Jk∈S1.
Ifk=1, then CmaxLPT=Cmax∗.
For the case ofk≥2, assume sk denotes the starting time of Jk. Since there is no idle time on the machines prior to the time sk,(1)sk≤∑j=1k−1pj+∑j=n1+1npj2=∑j=1kpj+∑j=n1+1npj−pk2≤∑j=1n1pj+∑j=n1+1npj−pk2≤Cmax∗−pk2.
Consider the following two cases:pk≤Cmax∗/2 and pk>Cmax∗/2.
Whenpk≤Cmax∗/2, we have(2)CmaxLPT=sk+pk≤Cmax∗−pk2+pk=Cmax∗+pk2≤Cmax∗+Cmax∗4=5Cmax∗4.
Whenpk>Cmax∗/2, based on optimal consideration, we have ∑j=n1+1npj≤Cmax∗/2 and each machine cannot arrange two jobs that belong to S1 and whose job’s index is less or equal to k. Therefore, Jk is the only job that belongs to S1 and being processed on M2. That is, CmaxLPT=pk+∑j=n1npj. Within the optimal sequence, Jk is the only job that belongs to S1 and can be processed on M2. We have Cmax∗≥CmaxLPT. Hence, Cmax∗=CmaxLPT.


## 3.2. The Computational Experiments

Although the worst case above seems quite good from the theoretical aspects, 25% errors cannot be accepted from the application dimensions. Therefore, some computational experiments were conducted to evaluate the performance of the LPT approach. The LPT approach was coded in Visual BASIC 6.0 and implemented on a personal computer with Intel corei7 16G CPU. Some test problems for each environment were randomly generated, the details of which are as follows:(1)
n is equal to 50, 100, 150, 200, 250, 300, 500, and 1000(2)
n1 is uniformly distributed over [1, n]. n2=n−n1(3)
pi is uniformly distributed over [1, 50], [1, 100], [1, 200], [1, 500], and [1, 1000]A ratio ofCmaxLPT−LB×100/LB is used as an index to evaluate the performance of the LPT approach, where CmaxLPT is the solution found by the LPT approach and LB is the solution found by lower bound. The ratio is computed for 300 test problems in each problem size; hence, 12000 (300 × 8 × 5) test problems are generated for the proposed problem P2fcCmax. The computational results are shown in Table 1. The results revealed that the mean percentage errors of the LPT approach are 0.0214, 0.0397, 0.0560, 0.0741, and 0.0905 with five different processing time distribution periods, respectively. From Table 1, we found that the larger the problem the smaller the error percentages and the wider the processing time range the larger the error percentages. The overall mean percent error of the LPT approach is 0.0565%.Table 1
Computational results of the LPT approach with five different processing time distribution periods.
npiU (1, 50)U (1, 100)U (1, 200)U (1, 500)U (1, 1000)Average500.09710.18840.28170.37140.45760.27921000.02700.04920.07150.09390.11670.07161500.01560.02640.03720.04830.05800.03712000.01050.01740.02360.02950.03500.02322500.00810.01320.01750.02110.02470.01693000.00660.01070.01370.01630.01890.01325000.00400.00590.00710.00800.00890.006810000.00220.00330.00380.00410.00430.0035Average0.02140.03970.05700.07410.09050.0565


## 4. Minimization of the Total Completion Time

In this section, we showed that the problemP2fcTC can be solved in On4 time. Let k1,k2 denotes the vector of the number of jobs allocated to M1 and M2, where 1≤k1≤n1 and n2≤k2≤n−1. We excluded the case of k1,k2=0,n because it becomes a single machine scheduling problem and the SPT (shortest processing time first) is optimal. Let Jij and pij denote a job scheduled in the jth position on a machine i and its processing time, respectively. For the convenience, we rename the job sequences processing on M1 and M2 as J11,J12,...,J1k1 and J21,J22,...,J2k2, respectively. Then, the total completion time can be calculated as follows:(3)TC=∑Cj=∑j=1k1k1−j+1p1j+∑j=1k2k2−j+1p2j.We rewrite equation (3) as(4)TC=∑Cj=∑j=1nwjpj,where(5)wj=k1−j+1,1≤j≤k1,n−j+1,k1+1≤j≤n,pj=p1j,1≤j≤k1,p2j−k1,k1+1≤j≤n.Assume the position of job that is processing onM1 and M2 is 1,…,k1 and k1+1,k1+2,,k1,k2n, respectively. Obviously, the second class of jobs cannot be scheduled at the previous position of k1. Then, we gave the elements of assignment vector as follows:(6)aij=wjpi,1≤i≤n1,1≤j≤n,∞,n1+1≤i≤n,1≤j≤k1,wjpi,n1+1≤i≤n,k1+1≤j≤n,where(7)wj=k1−j+1,1≤j≤k1n−j+1,k1+1≤j≤n.Constraint of the second line ataij ensures that the second class jobs are not scheduled before the position of k1 under minimization consideration. For a given vector k1,k2, P2fcTC can be formulated as the following assignment problem:(8)minimize∑i=1n∑j=1naijxij,∑i=1nxij=1,j=1,...,n∑j=1nxij=1,i=1,...,nxij=1,if jobiis scheduled in positionj,0..It is well-known that an assignment problem can be solved inOn3 time. For a given vector of k1,k2, 1≤k1≤n1, and n2≤k2≤n−1, problem P2fcTC can be solved in On3 time. There are n1 possible vectors of k1,k2, that is, 1,n−1,...,n1,n−n1. Hence, problem P2fcTC can be solved in On1n3 time, since n1≤n. This implies that the following theorem holds.Theorem 3.
ProblemP2fcTC can be solved in On4 time.Example 1.
AssumeN=S1∪S2, S1=J1,J2,J3, S2=J4,J5,J6,J7,J8,J9,J10, n=10, n1=3, and n2=7, and their processing time is listed in Table 2.
The following solution reports were obtained from Lingo 14.0 package. Ifk1,k2=1,9, then TC=290. If k1,k2=2,8, then TC=262. Therefore, the optimal solution is 262.
The optimal sequences those scheduling onM1 and M2 are J3⟶J2 and J10⟶J9⟶J8⟶J7⟶J6⟶J5⟶J4⟶J1, respectively.
The Lingo programming code underk1,k2=2,8 is listed as follows:Table 2
The 10 jobs processing time.
i12345678910pi5040307654321


## 5. Conclusions

This paper explored two parallel-machine scheduling problems with function constraint. We pointed out that the function constraint occurs not only in the manufacturing system but also in the service system. Therefore, this work is meaningful.In this research, two important and famous classical objectives, the makespan and the total completion time, were studied. For the makespan problem, we demonstrated that it is NP-hard in the ordinary sense. We presented a polynomial time heuristic for this problem and have proved its worst-case ratio is not greater than 5/4. Computational testing of the heuristic was conducted, and the results revealed that the overall mean percent error of the proposed algorithm is 0.0565%. For the total completion time problem, we have proved that it can be solved inOn4 time.Future research may examine other topics such as the total load, total tardiness, and number of tardy jobs or extending the model to the uniform parallel-machine setting or other settings.



---

*Source: 2717095-2020-05-18.xml*