BicriteriaHeuristic for Unrelated Parallel Machine Scheduling Problem

Abstract:

Article Preview

In this research, a bi-criteria heuristic is proposed to find non-dominated solutions for scheduling unrelated parallel machines with release dates that minimizes makespan andtotal weighted tardiness.

Info:

Periodical:

Edited by:

Dashnor Hoxha, Francisco E. Rivera and Ian McAndrew

Pages:

824-828

Citation:

Y. K. Lin and H. C. Lin, "BicriteriaHeuristic for Unrelated Parallel Machine Scheduling Problem", Advanced Materials Research, Vol. 1016, pp. 824-828, 2014

Online since:

August 2014

Export:

Price:

$38.00

* - Corresponding Author

[1] R. Graham, E. Lawler, J. Lenstra, K.A. Rinnooy. Optimization and approximationin deterministric sequencing and scheduling: A survey. Ann Discrete Math5, 287-326(1979).

[2] E. Angel, E. Bampis, A. Kononov. A FPTAS for approximating the unrelated parallel machines scheduling problem with costs. in: Proceeding of European Symposium on Algorithms (ESA) 2001, Springer, Berlin 194-205(2001).

DOI: https://doi.org/10.1007/3-540-44676-1_16

[3] E. Angel, E. Bampis, A. Kononov. On the approximate tradeoff for bicriteria batching and parallel machine scheduling problems. Theoretical Computer Science306(1), 319-338(2003).

DOI: https://doi.org/10.1016/s0304-3975(03)00288-3

[4] P.C. Chang S.H. Chen K.L. Lin. Two-phase sub population genetic algorithm for parallel machine-scheduling problem. Expert Systems with Applications 29, 705-712(2005).

[5] E.G. Coffman,R. Sethi. Algorithms minimizing mean flow time: schedulelength properties. Acta Informatica 6, 1-14(1976).

[6] B. Eck, M. Pinedo. On the minimization of the makespan subject to flowtime optimality. Operations Research 41, 797-800(1993).

[7] J. Gao. A novel artificial immune system for solving multiobjective scheduling problems subject to special process constraint. Computers and Industrial Engineering 58, 602-609(2010).

[8] J. Gao, G. He, Y. Wang. A new parallel genetic algorithm for solving multiobjective scheduling problems subjected to special process constraint. The International Journal of Advanced Manufacturing Technology 43, 151-160(2009).

[9] J.N.D. Gupta, J.C. Ho. Minimizing makespan subject to minimum flowtime on two identical parallel machines. Computers and Operations Research 28, 705-717(2001).

[10] J.N.D. Gupta J.C. Ho, S. Webster. Bicriteria optimisation of the makespan and mean flowtime on two identical parallel machines. Journal of the Operational Research Society 51, 1330-1339(2000).

DOI: https://doi.org/10.1057/palgrave.jors.2601016

[11] J.N.D. Gupta, A.J. Ruiz-Torres. Minimizing makespan subject to minimum total flow-time on identical parallel machines. European Journal of Operational Research 125, 370-380(2000).

DOI: https://doi.org/10.1016/s0377-2217(99)00386-0

[12] K. Jansen, L. Porkolab. Improved approximation schemes for scheduling unrelated parallel-machines. ACM Symposium on Theory of Computing 408-417(1999).

DOI: https://doi.org/10.1145/301250.301361

[13] J.Y.T. Leung, K. Lee, M.L. Pinedo. Bicriteria scheduling with machine assignment costs. International Journal of Production Economics 139, 321-329(2012).

DOI: https://doi.org/10.1016/j.ijpe.2012.05.016

[14] LinC.H., LiaoC.J., 2004. Makespan minimization subject to flowtime optimality on identical parallel machines. Computers and Operations Research 31, 1655-1666.

[15] D. Cao, M. Chen, G. Wan. Parallel machine selection and job scheduling to minimize machine cost and job tardiness. Computers and Operations Research 32, 1995-2012(2005).

[16] J.N.D. Gupta, A.J. Ruiz-Torres. Generating efficient schedules for identical parallel machines involving flow-time and tardy jobs. European Journal of Operational Research 167, 679-695(2005).

DOI: https://doi.org/10.1016/j.ejor.2004.07.015

[17] Y.K. Lin, J.W. Fowler, M.E. Pfund. Multiple-objective heuristics for scheduling unrelated parallel machines. European Journal of Operational Research (In Press). Doi: 10. 1016/j. ejor. 2012. 10. 008(2013).

DOI: https://doi.org/10.1016/j.ejor.2012.10.008

[18] A.J. Ruiz-Torres, E. E. Enscore, R.R. Barton. Simulated annealing heuristics for the average flow-time and the number of tardy jobs bicriteria identical parallel machine problem. Computers and Industry Engineering 33, 257–260(1997).

[19] J.K. Lenstra, A.R. Kan, P. Bricker. Complexity of machine scheduling problems. Ann Discrete Math 1, 343-362(1977).

[20] M. Nawaz, E.E. Jr. Enscore, I. Ham. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega 11(1), 91-95(1983).

DOI: https://doi.org/10.1016/0305-0483(83)90088-9

[21] Y.K. Lin, C.W. Lin. Dispatching rules for unrelated parallel machine scheduling with release dates. The International Journal of Advanced Manufacturing Technology67, 269-279(2013).

DOI: https://doi.org/10.1007/s00170-013-4773-8

[22] L. Mönch, H. Balasubramanian, J.W. Fowler M.E. Pfund. Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times. Computers and Operations Research32, 2731-2750(2005).

DOI: https://doi.org/10.1016/j.cor.2004.04.001