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

Authors: Farhad Kolahan, Vahid Kayvanfar

Abstract:

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.

Keywords: Makespan, Parallel machines, Scheduling, Simulated Annealing

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1082473

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.