Jibo Wang¹, Chou-Jung Hsu^2*
1School of Science, Shenyang Aerospace University, Shenyang, China.
²Department of Industrial Management, Nan Kai University of Technology, Nantou.
DOI: 10.4236/jamp.2016.41004   PDF    HTML   XML   4,684 Downloads   5,553 Views   Citations

Abstract

In this paper, we consider scheduling problems with general truncated job-dependent learning effect on unrelated parallel-machine. The objective functions are to minimize total machine load, total completion (waiting) time, total absolute differences in completion (waiting) times respectively. If the number of machines is fixed, these problems can be solved in  time respectively, where m is the number of machines and n is the number of jobs.

Keywords

Scheduling, Unrelated Parallel Machines, Truncated Job-Dependent Learning

Share and Cite:

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

(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

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.

Conflicts of Interest

The authors declare no conflicts of interest.

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