1 Introduction

1.1 Scheduling problem in the model of identical, parallel machines

In the real world, there are many examples of parallel-machine processing, e.g. a gas station can serve several cars simultaneously; bank counters can serve several customer at the same time; and automotive assembly lines can assemble several identical or nonidentical car models. In the classic parallel-machine processing model, there are two different conditions for the machines that are used: all the machines are identical or the machines may be nonidentical.

Many studies have been presented in the area of parallel-job scheduling. Some of these studies investigated ways of solving more classic problems with different performance measures [1, 2, 3, 4, 5, 6, 7]. Others studied such problems with some additional constraints [8, 9]. Yamada and Nakano [10] presented a genetic algorithm for the job-shop scheduling problem. Sule and Vijayasundaram [11] specifically dealt with a different scheduling problem that involved n jobs in m machine centres where each machine centre may have k number of identical processors. Iwamoto [12], Yamada and Nakeno [13], and Jain and Meeran [14] used different methods, such as fuzzy decision-making, deterministic local search, and neural networks, to solve specific problems.

In parallel-machine processing situations, minimising the total tardiness of the schedule is a very complicated and difficult thing. Gupta and Rothkopf [15, 16] suggested that the dynamic programming method could be used to get an optimal solution. However, even a very small problem (i.e. the numbers of machines and jobs are small), substantial computing is needed to get the solution. Therefore, Dogramaci and Sukis [17] proposed a heuristic to solve this kind of problem. Even this does not promise an optimal solution; however, the solution obtained will be the optimal solution or is not far away from it. In addition, the time consumed by using the heuristic is negligible compared to the dynamic programming or exhaustive methods.

1.2 Worker assignment scheduling problems

In the classic scheduling problem [18, 19, 20], no matter how many machines (work stations, processors, etc.) are involved, the number of operators (workers) at each machine may be ignored or assumed to be fixed and is not taken into consideration. However, in some cases, assigning more workers to work on the same job will decrease job completion time. Hence, ignoring worker assignment decision in these cases may cause managerial problems. In order to solve those problems and optimise the overall performance, decisions about job scheduling and worker assignment need to be resolved together.

In Hu’s [21] research, the scope of classic scheduling problems had been extended in that the assumption of constant job processing time was no longer necessary. Under the original assumption, job processing time was not affected by the number of workers work on the job. But Hu’s research suggested that there exist certain relationships between job processing time and the number of workers assigned to work on the job. Hence, job processing time is no longer a constant but related to the number of workers assigned to work on the job. Therefore, the worker assignment scheduling problem needs to solve two subproblems: how to assign jobs to machines and how to assign workers to machines.

1.3 Purposes of this study

This research focusses on the model of identical, parallel machines and uses total tardiness as the performance measure, that is, how to effectively assign the jobs and workers to machines to minimise the total tardiness in the model of identical, parallel machines.

This research has two purposes: one is to establish a mathematical model to describe the specific problem presented; the other is to develop efficient and effective heuristics to solve these two subproblems. In addition, hopefully, these heuristics can be adopted by industries to solve related problems.

2 Identical, parallel-machine processing worker assignment scheduling problem

The only difference between the worker assignment scheduling problem and the classic scheduling problem is that the former has an additional worker assignment problem. Hence, the processing times of jobs are no longer constants but related to the number of workers assigned to work on the job. Assumptions of the identical, parallel-machine processing worker assignment scheduling problem are as follows [21]:

  1. 1.

    Each job needs only one operation.

  2. 2.

    Each job only needs to be processed by one machine.

  3. 3.

    Any machine can process any job.

  4. 4.

    No machine may process more than one job at a time.

  5. 5.

    Machines will never break down and are available throughout the scheduling period.

  6. 6.

    Job processing times are independent of the job sequence.

  7. 7.

    Machine set-up time is negligible.

  8. 8.

    Transportation time between machines is negligible.

  9. 9.

    Number of jobs is fixed.

  10. 10.

    Number of machines is fixed.

  11. 11.

    There is a group of W workers that have the same abilities to perform the duties assigned to them.

  12. 12.

    W is within reasonable bounds, i.e. m≦W≦W c. W c is the maximum capacity of the resource.

  13. 13.

    These m machines, n jobs, and W workers are available at time zero.

  14. 14.

    The processing time function has a simplified form of t i (W j )=A i +B i /(E i ×W j ), where t i (W j ) is the processing time of job i that is processed on machine j in which the number of W j workers are assigned to it, A i is a fixed constant and not affected by the number of workers, B i /(E i ×W j ) is the variable part and affected by the number of workers. In addition, t i (W j )=A i +B i /(E i ×W j ) is assumed to be a decreasing function, i.e. A i ≧0, B i >0, E i ≧1.

  15. 15.

    If any machine has work waiting to be processed, workers must be assigned to this machine to process the job. The machine cannot be kept idle.

  16. 16.

    The number of workers assigned to each machine needs to be decided before any job can be processed and they will not be reassigned until all the jobs have been completed.

2.1 The mathematical model for minimising the total tardiness in the model of the identical, parallel-machine processing worker assignment scheduling problem

Before solving this specific identical, parallel-machine processing worker assignment scheduling problem, its mathematical model should be constructed to understand the problem’s characteristics. The performance measure used for this specific problem is total tardiness. If the tardiness of the k th job assigned to machine M j is T j,[k] and T j,[k]=max{0, C j,[k](W j )−d j,[k]}, then the total tardiness will be \({{\sum\limits_{j = 1}^m {{\sum\limits_{k = 1}^{Nj} {T_{{j{\left[ k \right]}}} } }} } = {\sum\limits_{j = 1}^m {{\sum\limits_{k = 1}^{Nj} {\,\,\,\max {\left\{ {0,C_{{j{\rm{,}}{\left[ k \right]}}} {\left( {W_{j} } \right)} - d_{{j{\rm{,}}{\left[ k \right]}}} } \right\}}} }} }.}\) In addition, let x i,j,[k]=1 when job J i is the k th job assigned to machine M j , and x i,j,[k]=0, otherwise. And let \({Y = {\sum\limits_{j = 1}^m {{\sum\limits_{k = 1}^{Nj} {\,\,\,T_{{j{\rm{,}}{\left[ k \right]}}} .} }} }} \) Then, the mathematical model of minimising total tardiness of the identical, parallel-machine processing worker assignment scheduling problem is as follows:

$$\min \,\,\,\,\,\,Y$$

subject to:

$$ {\sum\limits_{j = 1}^m {Nj = n} } $$

  • The sum of the jobs assigned to all machines is n.

$$ {\sum\limits_{j = 1}^m {Wj = W} } $$

  • All the W workers must be assigned.

$${\sum\limits_{j = 1}^m {{\sum\limits_{k = 1}^{Nj} {{\rm{ }}x_{{i{\rm{,}}j{\rm{,}}{\left[ k \right]}}} } }} } = 1\;\;\;\;\;\;i = 1,\; \ldots ,\;n $$

  • Each job can only be assigned to one machine and its processing order is k th on that machine.

$${\sum\limits_{i = 1}^n {{\sum\limits_{k = 1}^{Nj} {{\rm{ }}x_{{i{\rm{,}}j{\rm{,}}{\left[ k \right]}}} } }} } = N_{j} \;\;\;\;\;\;j = 1,\; \ldots ,\;m $$

  • There are N j jobs that are assigned to machine M j .

$${{\sum\limits_{i = 1}^n {{\sum\limits_{j = 1}^m {{\sum\limits_{k = 1}^{Nj} {\,\,{\rm{ }}x_{{i{\rm{,}}j{\rm{,}}{\left[ k \right]}}} } }} }} } = n}$$

  • All the n jobs need to be assigned completely.

  • x i,j,[k]=1 or 0, N j andW j are integers greater than 0.

According to Garey and Johnson [22], the specific problem presented in this research is NP-complete. Since there is no way to obtain the optimal solution other than with a mathematical model, heuristics, a guided random/iterative search such as GA (genetic algorithm), or simulated annealing could be used to solve this problem.

2.2 Heuristic for minimising the total tardiness in the model of identical, parallel-machine processing worker assignment scheduling problem

Since this research has two subproblems, how to assign jobs and how to assign workers, the descriptions of these two subproblems will follow accordingly. First, the job assignment subproblem will be explored. In order to solve this subproblem the heuristic developed by Dogramaci and Surkis [17] can be applied after some modifications.

2.2.1 Procedure 1 (for assigning n jobs):

Step 1.

List these n jobs in an order using priority rules SPT, EDD, and SLACK in sequence. Let W j =W for the processing time functions of all jobs.

Step 2.

Among those jobs that have not yet been assigned to a machine choose the first one in the ordered list, assign it to the earliest available machine, then remove it from the ordered list. Repeat this step until all n jobs are assigned.

Step 3.

Consider separately each of the m machines with the jobs assigned to it in step 2. Treat each as an individual single-processor tardiness problem, and resequence the assigned jobs to minimise the total tardiness.

Since the procedure presented above is mainly an application of SPT, EDD, and SLACK rules, it is referred to as the SES heuristic. After all n jobs have been assigned, we turn to the worker assignment subproblem. The solving procedures are as follows.

2.2.2 Procedure 2 (for assigning W workers):

Step 1.

Assign one worker to every machine that has job on it; therefore, m workers are assigned.

Step 2.

Assign the next worker to the machine that can minimise the total tardiness.

Step 3.

Repeat step 2 until all these W workers have been assigned completely.

Step 4.

Consider separately each of the m machines with the jobs assigned to it in step 3. Treat each as an individual single-processor tardiness problem, and resequence these assigned jobs to minimise the total tardiness.

Because the W workers are assigned according to their marginal contribution (i.e. the amount of total tardiness reduced by adding one more worker.), the procedure can be referred to as the largest marginal contribution procedure (LMC procedure).

2.2.3 Procedure 3 (for choosing the final solution):

Step 1.

If the total tardiness of the schedule obtained in procedure 2 reaches zero, the schedule is the final solution. Otherwise, repeat procedures 1 and 2 until all the priority rules have been applied.

Step 2.

If none of these schedules yields zero total tardiness, compare the total tardiness generated by these schedules. The schedule with the least total tardiness is the final solution.

3 Performance evaluation of the heuristics developed

In order to evaluate the performance of the heuristics developed in the previous section, the method of evaluation and the result of the evaluation will be described in the following text.

3.1 Method of evaluation

In this research, a simulation procedure is used to evaluate the performance of these heuristics; the procedure is illustrated as follows.

Step 1.

Assume that the processing time function of any job J i is t i (W j )=A i +B i /(E i ×W j ), where A i , B i , and E i follow uniform distribution and 0≦A i <100, 1≦B i <100, and 1≦E i <100. Due date d i =A i +B i /(E i ×W)+ an integer between 1 and 99. This is because due date cannot be less than the least possible processing time.

Step 2.

All the values of A i , B i , E i and the integer part of d i are generated randomly.

Step 3.

100 sets of worker assignment scheduling problems have been generated and each of them has the following characteristic: there are 10 workers available, 6 jobs waited to be processed, and 3 machines ready to process the jobs.

Step 4.

An improved exhaustive search method is used to find the optimal solution for each of the 100 simulated problems. For example, some of the improvements are: jobs assigned to each machine will be adjusted to follow the EDD rule and once the total tardiness of any schedule reaches zero the searching process is terminated. Therefore, it is sometimes not necessary to exhaust all the possible schedules to get the optimal solution. Then, the heuristics are used to find the solutions of the 100 simulated problems. In order to compare the performance of these two, two performance measures are used:

  1. 1.

    Ratio 1 = total tardiness / least possible total processing time

$${\rm{Ratio}}\;{\rm{1}} = \Sigma t_{i} /\Sigma {\left[ {A_{i} + B_{i} /{\left( {E_{i} \times W} \right)}} \right]} $$
  1. 2.

    Ratio 2 = total tardiness / most possible total slack time

$${{\rm{Ratio}}\;{\rm{2}} = \Sigma t_{i} /\Sigma {\left\{ {d_{i} - {\left[ {A_{i} + B_{i} /{\left( {E_{i} \times W} \right)}} \right]}} \right\}}} $$

These two performance measures allow the results obtained from the improved exhaustive method and heuristics to be compared under the same conditions. In addition, ratio 1 and ratio 2 can show the percentage and severity of the total tardiness compared to the least possible total processing time and the most possible total slack time.

Step 5.

Compare the values of ratio 1 and ratio 2 of these 100 sets of simulated problems obtained from the improved exhaustive search method and heuristics.

3.2 Result of the evaluation

The results of first 30 sets of these 100 sets of simulated problems are shown in Tables 1, 2, and 3. According to the results, 88 of the 100 sets of simulated problems obtain the optimal solutions no matter whether the improved exhaustive search method or the heuristics is used. For the remaining 12 sets, the average difference between the exhaustive search method and the heuristics are 0.0172 for ratio 1 and 0.0254 for ratio 2; all are smaller than 3%. That is, even though the solutions obtained from the heuristics are not optimal, they are not far from it. In addition, by using a PC with Intel Pentium 4 2.00 GHz CPU, it only took 4 s using the heuristics compared to 117 s using the improved exhaustive search method; a 96.58% savings. Therefore, the heuristics developed in this research are efficient and effective.

Table 1. Results of 1–12 sets of the simulated problems
Full size table
Table 2. Results of 13-24 sets of the simulated problems
Full size table
Table 3. Results of 25-30 sets of the simulated problems
Full size table

4 Conclusion

In this research, worker assignment scheduling problems are presented, defined, and formulated. Since only the exhaustive search method can obtain optimal solutions to these problems, heuristics have been developed. After the simulation, results have shown that the heuristics developed in this research can obtain optimal or near optimal solutions for these simulated problems.

In the future, the conclusions of this research may be extended to scheduling problems in the real world. The task may be highly complicated; nonetheless, it will be an interesting and challenging mission.