A Heuristic Algorithm Approach for Scheduling of Multi-criteria Unrelated Parallel Machines

In this paper we address a multi-objective scheduling problem for unrelated parallel machines. In unrelated parallel systems, the processing cost/time of a given job on different machines may vary. The objective of scheduling is to simultaneously determine the job-machine assignment and job sequencing on each machine. In such a way the total cost of the schedule is minimized. The cost function consists of three components, namely; machining cost, earliness/tardiness penalties and makespan related cost. Such scheduling problem is combinatorial in nature. Therefore, a Simulated Annealing approach is employed to provide good solutions within reasonable computational times. Computational results show that the proposed approach can efficiently solve such complicated problems.





References:
[1] Brucker, P. Scheduling Algorithms, Second ed., Springer, Berlin. 1998
[2] Koulamas, C. The total tardiness problem: Review and extensions.
Operations Research 42 (6): 1025-1041, 1994.
[3] Sen, T. & Sulek, J.M. & Dileepan, P. Static scheduling research to
minimize weighted and unweighted tardiness: A state-of-the-art survey.
International Journal Production Economics 83: 1-12, 2002.
[4] Tamer, E. A bi-criteria parallel machine scheduling with a learning
effect of setup and removal times. Applied Mathematical Modeling 33:
1141-1150, 2009.
[5] Varadharajan, T.K. & Chandrasekharan, R. A multi-objective simulatedannealing
algorithm for scheduling in flow shops to minimize the
makespan and total flow time of jobs. European Journal of Operational
Research 167: 772-795, 2005.
[6] Pinedo, M. Scheduling: Theory, Algorithms and Systems. Prentice-Hall,
NJ, 1995.
[7] Eun-Seok, K. & Chang-Sup, S. & Ik-Sun, L. Scheduling of parallel
machines to minimize total completion time subject to s-precedence
constraints. Computers & Operations Research 36: 698 - 710, 2009.
[8] Kai, L. & Shan-lin, Y. Non-identical parallel-machine scheduling
research with minimizing total weighted completion times: Models,
relaxations and algorithms. Applied Mathematical Modeling 33: 2145-
2158, 2009.
[9] Logendran, R. & McDonell, B. & Smucker, B. Scheduling unrelated
parallel machines with sequence-dependent setups. Computers &
Operations Research 34: 3420-3438, 2007.
[10] Liaw, C.F. & Lin, Y.K. & Cheng, C.Y. & Chen, M. Scheduling
unrelated parallel machines to minimize total weighted tardiness.
Computers and Operations Research 30: 1777-1789, 2003.
[11] Morton, T.E. & Pentico, D.W. Heuristic Scheduling Systems. John
Wiley & Sons, NY, 1993.
[12] Pinedo, M. & Singer, M. A shifting bottleneck heuristic for minimizing
the total weighted tardiness in a job shop. Naval Research Logistics 46
(1): 1-17, 1999.
[13] Yang, T. & He, Z. & Cho, K.K. An effective heuristic method for
generalized job shop scheduling with due dates. Computers and
Industrial Engineering 26 (4): 647-660, 1994.
[14] Gurel, s. & Akturk, M. S. Optimal allocation and processing time
decisions on non-identical parallel CNC machines. European Journal of
Operational Research 183: 591-607, 2007.
[15] Cochran, J. K. & Horng, S. & Fowler, J. W. A multi-population genetic
algorithm to solve multi-objective scheduling problems for parallel
machines. Computers & Operations Research 30: 1087-1102, 2003.
[16] Loukil, T. & Teghem, J. & Tuyttens, D. Solving multi-objective
production scheduling problems using meta heuristics. European Journal
of Operational Research 161: 42-61, 2005.
[17] Kirkpatrick & Gelatt, J. & Vecchi, d.D. Optimization by simulated
annealing. Science 220: 671-680, 1983.