• Previous Article
    Existence and convergence results for best proximity points in cone metric spaces
  • NACO Home
  • This Issue
  • Next Article
    Parameter identification of nonlinear delayed dynamical system in microbial fermentation based on biological robustness
2014, 4(2): 115-132. doi: 10.3934/naco.2014.4.115

Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration

1. 

Western Australia Centre of Excellence in Industrial Optimization(WACEIO), Department of Mathematics and Statistics, Curtin University, GPO Box U1987 Perth, WA 6845, Australia

2. 

Department of Mathematical Sciences, Faculty of Science, University Technology Malaysia, 81310 UTM Johor Bahru, Johor, Malaysia

Received  January 2013 Revised  January 2014 Published  May 2014

In this paper, we consider a non-preemptive task scheduling problem for unrelated parallel processors (UPP) with the objective of minimizing the makespan. We address priority consideration as an added feature to the basic task characteristics of UPP scheduling. A mixed integer linear programming model is developed to obtain an optimal solution for the problem. Computational testing is implemented using AIMMS 3.10 package and CPLEX 12.1 as the solver. Computational results show that the proposed MILP model is effective and produces optimal results with up to 100 tasks run on 5 processors with an average solution time of less than an hour.
Citation: Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115
References:
[1]

European Journal of Operational Research, 187 (2008), 985-1032. doi: 10.1016/j.ejor.2006.06.060.  Google Scholar

[2]

Proceedings of the 5th Biannual world automation congress, 14 (2002), 115-120. Google Scholar

[3]

Ph. D thesis, Chalmers University of Technology in Goteborg, Sweden, 2003. Google Scholar

[4]

Algorithmica, 55 (2005), 205-226. doi: 10.1007/s00453-007-9004-y.  Google Scholar

[5]

European Journal of Operational Research, 51 (1991), 283-300. Google Scholar

[6]

in Handbook of Combinatorial Optimization (Vol. 3) (eds. D.-Z. Du and P. M. Pardalos), Kluwer Academic Publishers, (1998), 21-169.  Google Scholar

[7]

European Journal of Operational Research, 165 (2005), 457-467. Google Scholar

[8]

Mathematical and Computer Modelling, 20 (1994), 41-52. Google Scholar

[9]

European Journal of Operational Research, 139 (2002), 1-25. doi: 10.1016/S0377-2217(01)00181-3.  Google Scholar

[10]

Annals of Discrete Mathematics, 5 (1979), 287-326.  Google Scholar

[11]

Lecture Notes in Computer Science, (2005), 182-192. doi: 10.1007/11496915_14.  Google Scholar

[12]

European Journal of Operational Research, 102 (1997), 528-537. Google Scholar

[13]

European Journal of Operational Research, 94 (2003), 361-374. doi: 10.1007/s10107-002-0324-z.  Google Scholar

[14]

Mathematical Programming, 46 (1990), 259-271. doi: 10.1007/BF01585745.  Google Scholar

[15]

Robotics and Computer Integrated Manufacturing, 19 (2003), 173-181. Google Scholar

[16]

European Journal of Operational Research, 54 (2003), 23-38. Google Scholar

[17]

Journal of the Association for Computing Machinery, 25 (1978), 621-619. doi: 10.1145/322092.322101.  Google Scholar

[18]

Applied mathematical Modelling, 33 (2009), 2145-2158. doi: 10.1016/j.apm.2008.05.019.  Google Scholar

[19]

Annals of Operations Research, 117 (2002), 133-150. doi: 10.1023/A:1021569406280.  Google Scholar

[20]

Discrete Applied Mathematics, 75 (1997), 169-188. doi: 10.1016/S0166-218X(96)00087-X.  Google Scholar

[21]

Discrete Applied Mathematics, 10 (1985), 155-164. doi: 10.1016/0166-218X(85)90009-5.  Google Scholar

[22]

Mathematical Programming, 62 (1993), 461-474. doi: 10.1007/BF01585178.  Google Scholar

[23]

Journal of the Operational Research Society, 49 (1998), 886-894. Google Scholar

[24]

International Journal Advanced Technology, 43 (2009), 1189-1201. Google Scholar

[25]

IIE Transactions, 34 (2002), 921-931. Google Scholar

[26]

IEEE 19th International Symposium of Personal, Indoor and Mobile Radio Communication (PIMRC), (2008), 1-5. Google Scholar

show all references

References:
[1]

European Journal of Operational Research, 187 (2008), 985-1032. doi: 10.1016/j.ejor.2006.06.060.  Google Scholar

[2]

Proceedings of the 5th Biannual world automation congress, 14 (2002), 115-120. Google Scholar

[3]

Ph. D thesis, Chalmers University of Technology in Goteborg, Sweden, 2003. Google Scholar

[4]

Algorithmica, 55 (2005), 205-226. doi: 10.1007/s00453-007-9004-y.  Google Scholar

[5]

European Journal of Operational Research, 51 (1991), 283-300. Google Scholar

[6]

in Handbook of Combinatorial Optimization (Vol. 3) (eds. D.-Z. Du and P. M. Pardalos), Kluwer Academic Publishers, (1998), 21-169.  Google Scholar

[7]

European Journal of Operational Research, 165 (2005), 457-467. Google Scholar

[8]

Mathematical and Computer Modelling, 20 (1994), 41-52. Google Scholar

[9]

European Journal of Operational Research, 139 (2002), 1-25. doi: 10.1016/S0377-2217(01)00181-3.  Google Scholar

[10]

Annals of Discrete Mathematics, 5 (1979), 287-326.  Google Scholar

[11]

Lecture Notes in Computer Science, (2005), 182-192. doi: 10.1007/11496915_14.  Google Scholar

[12]

European Journal of Operational Research, 102 (1997), 528-537. Google Scholar

[13]

European Journal of Operational Research, 94 (2003), 361-374. doi: 10.1007/s10107-002-0324-z.  Google Scholar

[14]

Mathematical Programming, 46 (1990), 259-271. doi: 10.1007/BF01585745.  Google Scholar

[15]

Robotics and Computer Integrated Manufacturing, 19 (2003), 173-181. Google Scholar

[16]

European Journal of Operational Research, 54 (2003), 23-38. Google Scholar

[17]

Journal of the Association for Computing Machinery, 25 (1978), 621-619. doi: 10.1145/322092.322101.  Google Scholar

[18]

Applied mathematical Modelling, 33 (2009), 2145-2158. doi: 10.1016/j.apm.2008.05.019.  Google Scholar

[19]

Annals of Operations Research, 117 (2002), 133-150. doi: 10.1023/A:1021569406280.  Google Scholar

[20]

Discrete Applied Mathematics, 75 (1997), 169-188. doi: 10.1016/S0166-218X(96)00087-X.  Google Scholar

[21]

Discrete Applied Mathematics, 10 (1985), 155-164. doi: 10.1016/0166-218X(85)90009-5.  Google Scholar

[22]

Mathematical Programming, 62 (1993), 461-474. doi: 10.1007/BF01585178.  Google Scholar

[23]

Journal of the Operational Research Society, 49 (1998), 886-894. Google Scholar

[24]

International Journal Advanced Technology, 43 (2009), 1189-1201. Google Scholar

[25]

IIE Transactions, 34 (2002), 921-931. Google Scholar

[26]

IEEE 19th International Symposium of Personal, Indoor and Mobile Radio Communication (PIMRC), (2008), 1-5. Google Scholar

[1]

Longxiang Fang, Narayanaswamy Balakrishnan, Wenyu Huang. Stochastic comparisons of parallel systems with scale proportional hazards components equipped with starting devices. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021004

[2]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

[3]

Saeed Assani, Muhammad Salman Mansoor, Faisal Asghar, Yongjun Li, Feng Yang. Efficiency, RTS, and marginal returns from salary on the performance of the NBA players: A parallel DEA network with shared inputs. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021053

[4]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[5]

Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058

[6]

Marita Holtmannspötter, Arnd Rösch, Boris Vexler. A priori error estimates for the space-time finite element discretization of an optimal control problem governed by a coupled linear PDE-ODE system. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021014

[7]

Jianli Xiang, Guozheng Yan. The uniqueness of the inverse elastic wave scattering problem based on the mixed reciprocity relation. Inverse Problems & Imaging, 2021, 15 (3) : 539-554. doi: 10.3934/ipi.2021004

[8]

Vladimir Gaitsgory, Ilya Shvartsman. Linear programming estimates for Cesàro and Abel limits of optimal values in optimal control problems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021102

[9]

Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203

[10]

Qing Liu, Bingo Wing-Kuen Ling, Qingyun Dai, Qing Miao, Caixia Liu. Optimal maximally decimated M-channel mirrored paraunitary linear phase FIR filter bank design via norm relaxed sequential quadratic programming. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1993-2011. doi: 10.3934/jimo.2020055

[11]

Carlos Fresneda-Portillo, Sergey E. Mikhailov. Analysis of Boundary-Domain Integral Equations to the mixed BVP for a compressible stokes system with variable viscosity. Communications on Pure & Applied Analysis, 2019, 18 (6) : 3059-3088. doi: 10.3934/cpaa.2019137

[12]

Tong Li, Nitesh Mathur. Riemann problem for a non-strictly hyperbolic system in chemotaxis. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021128

[13]

Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $ k $-facility location problem with linear penalties. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056

[14]

Misha Bialy, Andrey E. Mironov. Rich quasi-linear system for integrable geodesic flows on 2-torus. Discrete & Continuous Dynamical Systems, 2011, 29 (1) : 81-90. doi: 10.3934/dcds.2011.29.81

[15]

Ahmad El Hajj, Hassan Ibrahim, Vivian Rizik. $ BV $ solution for a non-linear Hamilton-Jacobi system. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3273-3293. doi: 10.3934/dcds.2020405

[16]

Kuan-Hsiang Wang. An eigenvalue problem for nonlinear Schrödinger-Poisson system with steep potential well. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021030

[17]

Kehan Si, Zhenda Xu, Ka Fai Cedric Yiu, Xun Li. Open-loop solvability for mean-field stochastic linear quadratic optimal control problems of Markov regime-switching system. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021074

[18]

Shan-Shan Lin. Due-window assignment scheduling with learning and deterioration effects. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021081

[19]

Xiaoni Chi, Zhongping Wan, Zijun Hao. A full-modified-Newton step $ O(n) $ infeasible interior-point method for the special weighted linear complementarity problem. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021082

[20]

Hsin-Lun Li. Mixed Hegselmann-Krause dynamics. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021084

 Impact Factor: 

Metrics

  • PDF downloads (55)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]