Unrelated Parallel-Machine Scheduling Problems with General Truncated Job-Dependent Learning Effect

Show more

1. Introduction

In modern planning and scheduling problems, there are many real situations where the processing time of jobs may be subject to change due to learning effect. An extensive survey of different scheduling models and problems with learning effects could be found in Biskup [1]. More recently, Janiak et al. [2] studied a single processor problem with a S-shaped learning model. They proved that the makespan minimization problem is strongly NP-hard. Lee [3] considered scheduling jobs with general position-based learning curves. For some single machine and a two-machine flowshop scheduling problems, they presented the optimal solution respectively. Lee [4] considered single-machine scheduling jobs with general learning effect and past-sequence-dependent setup time. For some single machine scheduling problems, they presented the optimal solution respectively. Lee and Wu [5], and Wu and Lee [6] considered scheduling jobs with learning effects. They proved that some single machine and flowshop scheduling problems can be solved in polynomial time respectively. Lee et al. [7] considered a single-machine scheduling problem with release times and learning effect. Lee et al. [8] considered a makespan minimization uniform parallel-machine scheduling problem with position-based learning curves. Lee and Chung [9], Sun et al. [10] [11], and Wang et al. [12] considered flow shop scheduling with learning effects. Wu et al. [13], Wu et al. [14], Wu et al. [15] and Wang et al. [16] considered scheduling problems with the truncated learning effect.

Recently, Wang et al. [17] considered several scheduling problems on a single machine with truncated job-dependent learning effect, i.e., the actual processing time of job is if it is sche-

duled in the rth position of a sequence, where is the job-dependent learning index of job, and b is a truncation parameter with. In this paper, we study scheduling problems with general truncated job- dependent learning effect on unrelated parallel-machine. The objective is to minimize total machine load, total completion (waiting) time, total absolute differences in completion (waiting) times respectively.

2. Problems Description

There are n independent jobs to be processed on m unrelated paralle-machine . Let denote a job-allocation vector, where denotes the number of jobs assigned to machine, and. In this paper, we assume that the actual processing time of job scheduled on machine is

, (1)

where denotes the normal (basic) processing time of job on machine, is the position of a sequence, is a truncation parameter with, is the general case of positional learning for job on machine, special is the polynomial learning index for job on machine, is the exponential learning index for job on machine.

Let and be the completion and waiting time for job on machine respectively. The goal is to determine the jobs assigned to corresponding each machine and the corresponding optimal sche-

dule so that the following objective functions is to be minimized: the total machine load, the total completion (waiting) times, the total absolute differences in completion (waiting) times，where denotes the makespan of machine. Using the three-field notation [18] the problems can be denoted as, where denote the model (1),.

3. Main Results

Let denote the actual processing time of a job when it is scheduled in position on machine, then, , , are defined similarly.

Lemma 1. For a given permutation on machine,

(Kanet [19])

(Bagchi [20]).

If the vector is given, let be a variable such that if job is assigned at position on machine, and, otherwise. Then, the problem (where) can be solved by the following assignment problem:

(2)

(3)

(4)

or 1, (5)

where for, for, for, for, for.

Now, the question is how many vectors exist. Obviously may be 0, 1, 2, , n. So if the numbers of jobs assigned to the first machines is given, the number of jobs assigned to the last machine is then determined uniquely (). Therefore, the upper bound of is. Based on the above analysis, we have the following result.

Theorem 1. For a given constant, can be solved in time, where

.

Proof. As discussed above, to solve the problem, polynomial number (i.e.,) of assignment problems need to be solved. Each assignment problem is solved in time (by using the Hungarian method). Hence, the time complexity of the problem can be solved in time, where

.

Note that if the number of machines is fixed, then the problem can be solved in polynomial time. Based on the above analysis, we can determine the optimal solution for the problem via the following algorithm:

Algorithm 1

Step 1. For each possible vector, solve the assignment problem (2)-(5). Then, obtain the optimal schedule and the corresponding objective function.

Step 2. The optimal solution for the problem is the one with the minimum value of the objective function, where.

The following example illustrates the working of Algorithm 1 to find the optimal solution for the problem.

Example 1. There are jobs and, The number of machines is and, , , , , , , , , , , , , , , , , , , , are given.

Solution. When, the positional weights on machine are, , , ,. Then values are given in Table 1 (the bold value is the optimal solution of the assignment problem (2)-(5)).We solve the assignment problem (2)-(5) to

When, the positional weights on machine and are, , , ,. Then values are given in Table 2. We solve the assignment problem

Table 1. The values of Example 1. for.

Table 2. The values of Example 1 for.

(2)-(5) to obtain that the optimal schedule on machine is, and on machine is. The objective function is

When, the positional weights on machine and are, , , ,. Then values are given in Table 3. We solve the assignment problem (2)-(5) to obtain that the optimal schedule on machine is, and on machine is. The objective function is

When, the positional weights on machine and are, , , ,. Then values are given in Table 4. We solve the assignment problem (2)-(5) to obtain that the optimal schedule on machine is, and on machine is. The objective function is

When, the positional weights on machine and are, , , ,. Then values are given in Table 5. We solve the assignment problem (2)-(5) to obtain that the optimal schedule on machine is, and on machine is. The objective function is

When, the positional weights on machine and are, , , ,. Then values are given in Table 6. We solve the assignment problem (2)-(5) to obtain that the optimal schedule on machine is. The objective function is

Table 3. The values of Example 1 for.

Table 4. The values of Example 1 for.

Table 5. The values of Example 1 for.

Table 6. The values of Example 1 for.

Hence, the optimal schedule on machine is, and on machine is. The optimal objective function is

Acknowledgements

Hsu was supported by the Ministry Science and Technology of Taiwan under Grant MOST 104-2221-E-252- 002-MY2.

NOTES

^{*}Corresponding author.

References

[1] Biskup, D. (2008) A State-of-the-Art Review on Scheduling with Learning Effects. European Journal of Operational Research, 188, 315-329. http://www.sciencedirect.com/science/article/pii/S0377221707005280
http://dx.doi.org/10.1016/j.ejor.2007.05.040

[2] Janiak, A., Janiak, W., Rudek, R. and Wielgus, A. (2009) Solution Algorithms for the Makespan Minimization Problem with the General Learning Model. Computers and Industrial Engineering, 56, 1301-1308.
http://www.sciencedirect.com/science/article/pii/S0360835208001654
http://dx.doi.org/10.1016/j.cie.2008.07.019

[3] Lee, W.-C. (2011) Scheduling with General Position-Based Learning Curves. Information Sciences, 181, 5515-5522.
http://www.sciencedirect.com/science/article/pii/S0020025511004130
http://dx.doi.org/10.1016/j.ins.2011.07.051

[4] Lee, W.-C. (2011) A note on Single-Machine Scheduling with General Learning Effect and Past-Sequence-Dependent Setup Time. Computers and Mathematics with Applications, 62, 2095-2100.
http://www.sciencedirect.com/science/article/pii/S0898122111005384
http://dx.doi.org/10.1016/j.camwa.2011.06.057

[5] Lee, W.-C. and Wu, C.-C. (2009) Some Single-Machine and m-Machine Flowshop Scheduling Problems with Learning Considerations. Information Sciences, 179, 3885-3892.
http://www.sciencedirect.com/science/article/pii/S0020025509003235
http://dx.doi.org/10.1016/j.ins.2009.07.011

[6] Wu, C.-C. and Lee, W.-C. (2009) Single-Machine and Flowshop Scheduling with a General Learning Effect Model. Computers & Industrial Engineering, 56, 1553-1558.
http://www.sciencedirect.com/science/article/pii/S036083520800260X
http://dx.doi.org/10.1016/j.cie.2008.10.002

[7] Lee, W.-C., Wu, C.-C. and Hsu, P.-H. (2010) A Single-Machine Learning Effect Scheduling Problem with Release Times. Omega—The International Journal of Management Science, 38, 3-11.
http://www.sciencedirect.com/science/article/pii/S0305048309000024
http://dx.doi.org/10.1016/j.omega.2009.01.001

[8] Lee, W.-C., Yeh, W.-C. and Chuang, M.C. (2012) Uniform Parallel-Machine Scheduling to Minimize Makespan with Position-Based Learning Curves. Computers & Industrial Engineering, 63, 813-818.
http://www.sciencedirect.com/science/article/pii/S0360835212001283
http://dx.doi.org/10.1016/j.cie.2012.05.003

[9] Lee, W.-C. and Chung, Y.-H. (2013) Permutation Flowshop Scheduling to Minimize the Total Tardiness with Learning Effects. International Journal of Production Economics, 141, 327-334.
http://www.sciencedirect.com/science/article/pii/S0925527312003623
http://dx.doi.org/10.1016/j.ijpe.2012.08.014

[10] Sun, L.-H., Cui, K., Chen, J.-H., Wang, J. and He, X.-C. (2013) Research on Permutation Flow Shop Scheduling Problems with General Position-Dependent Learning Effects. Annals of Operations Research, 211, 473-480.
http://link.springer.com/article/10.1007/s10479-013-1481-6
http://dx.doi.org/10.1007/s10479-013-1481-6

[11] Sun, L.-H., Cui, K., Chen, J.-H., Wang, J. and He, X.-C. (2013) Some Results of the Worst-Case Analysis for Flow Shop Scheduling with a Learning Effect. Annals of Operations Re-search, 211, 481-490.
http://link.springer.com/article/10.1007/s10479-013-1368-6
http://dx.doi.org/10.1007/s10479-013-1368-6

[12] Wang, X.-Y., Zhou, Z., Zhang, X., Ji, P. and Wang, J.-B. (2013) Several Flow Shop Scheduling Problems with Truncated Position-Based Learning Effect. Computers & Operations Research, 40, 2906-2929.
http://www.sciencedirect.com/science/article/pii/S0305054813001743
http://dx.doi.org/10.1016/j.cor.2013.07.001

[13] Wu, C.-C., Yin, Y. and Cheng, S.-R. (2011) Some Single-Machine Scheduling Problems with a Truncation Learning Effect. Computers & Industrial Engineering, 60, 790-795.
http://www.sciencedirect.com/science/article/pii/S0360835211000362
http://dx.doi.org/10.1016/j.cie.2011.01.016

[14] Wu, C.-C., Yin, Y. and Cheng, S.-R. (2013) Single-Machine and Two-Machine Flowshop Scheduling Problems with Truncated Position-Based Learning Functions. Journal of the Operation Research Society, 64, 147-156.
http://www.palgrave-journals.com/jors/journal/v64/n1/abs/jors201246a.html
http://dx.doi.org/10.1057/jors.2012.46

[15] Wu, C.-C., Yin, Y., Wu, W.-H. and Cheng, S.-R. (2012) Some Polynomial Solvable Single-Machine Scheduling Problems with a Truncation Sum-of-Processing-Times Based Learning Effect. European Journal of Industrial Engineering, 6, 441-453. http://www.inderscienceonline.com/doi/abs/10.1504/EJIE.2012.047665
http://dx.doi.org/10.1504/ejie.2012.047665

[16] Wang, J.-B., Wang, X.-Y., Sun, L.-H. and Sun, L.-Y. (2013) Scheduling Jobs with Truncated Exponential Learning Functions. Optimization Letters, 7, 1857-1873. http://link.springer.com/article/10.1007/s11590-011-0433-9
http://dx.doi.org/10.1007/s11590-011-0433-9

[17] Wang, X.-R., Wang, J.-B., Jin, J. and Ji, P. (2014) Single Machine Scheduling with Truncated Job-Dependent Learning Effect. Optimization Letters, 8, 669-677. http://link.springer.com/article/10.1007/s11590-012-0579-0
http://dx.doi.org/10.1007/s11590-012-0579-0

[18] Graham, R.L., Lawler, E.L., Lenstra, J.K. and Rinnooy Kan, A.H.G. (1979) Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey. Annals of Discrete Mathematics, 5, 287-326.
http://www.sciencedirect.com/science/article/pii/S016750600870356X
http://dx.doi.org/10.1016/S0167-5060(08)70356-X

[19] Kanet, J.J. (1981) Minimizing Variation of Flow Time in Single Machine Systems. Management Science, 27, 1453- 1459. http://pubsonline.informs.org/doi/abs/10.1287/mnsc.27.12.1453
http://dx.doi.org/10.1287/mnsc.27.12.1453

[20] Bagchi, U.B. (1989) Simultaneous Minimization of Mean and Variation of Flow-Time and Waiting Time in Single Machine Systems. Operations Research, 37, 118-125. http://pubsonline.informs.org/doi/abs/10.1287/opre.37.1.118
http://dx.doi.org/10.1287/opre.37.1.118