• 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]

Ali Allahverdi, C. T. Ng, T. C. E. Cheng and Mikhail Y. Kovalyov, A survey of scheduling problems with setup times or costs,, European Journal of Operational Research, 187 (2008), 985.  doi: 10.1016/j.ejor.2006.06.060.  Google Scholar

[2]

Georgios C. Anagnostopoulos and Ghaith Rabadi, A simulated annealing algorithm for the unrelated parallel machine scheduling problem,, Proceedings of the 5th Biannual world automation congress, 14 (2002), 115.   Google Scholar

[3]

Bjorn Andersson, Static-priority Scheduling on Multiprocessors,, Ph. D thesis, (2003).   Google Scholar

[4]

V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy and Aravind Srivivasan, Scheduling on unrelated machines under tree-like precedence constraints,, Algorithmica, 55 (2005), 205.  doi: 10.1007/s00453-007-9004-y.  Google Scholar

[5]

Jacek Blazewicz, Moshe Dror and Jan Weglarz, Mathematical programming formulations for machine scheduling : A survey,, European Journal of Operational Research, 51 (1991), 283.   Google Scholar

[6]

Bo Chen, Chris N. Potts and Gerhard J. Woeginger, A review of machine scheduling: Complexity, algorithms and approximability,, in Handbook of Combinatorial Optimization (Vol. 3) (eds. D.-Z. Du and P. M. Pardalos), (1998), 21.   Google Scholar

[7]

M. Ghirardi and C. N. Potts, Makespan minimization for scheduling unrelated parallel machines: A recovering beam search approach,, European Journal of Operational Research, 165 (2005), 457.   Google Scholar

[8]

C. A. Glass, C. N. Potts and P. Shade, Unrelated parallel machine scheduling using local search,, Mathematical and Computer Modelling, 20 (1994), 41.   Google Scholar

[9]

Valery Gordon, Jean-Marie Proth and Chengbin Chu, A survey of the state-of-the-art of common due date assignement and scheduling research,, European Journal of Operational Research, 139 (2002), 1.  doi: 10.1016/S0377-2217(01)00181-3.  Google Scholar

[10]

R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey,, Annals of Discrete Mathematics, 5 (1979), 287.   Google Scholar

[11]

Alexander Grigoriev, Maxim Sviridenko and Marc Uetz, Unrelated parallel machine scheduling with resource dependent processing times,, Lecture Notes in Computer Science, (2005), 182.  doi: 10.1007/11496915_14.  Google Scholar

[12]

Jeffrey Herrmann, Jean-Marie Proth and Nathalie Sauer, Heuristic for unrelated machine scheduling with presedence canstraint,, European Journal of Operational Research, 102 (1997), 528.   Google Scholar

[13]

Han Hoogeveen, Martin Skutella and Gerhard J. Woeginger, Mathematical Programming,, European Journal of Operational Research, 94 (2003), 361.  doi: 10.1007/s10107-002-0324-z.  Google Scholar

[14]

Jan Karel Lenstra, David B Shmoys and Eva Tardos, Approximation algorithms for scheduling unrelated parallel machine,, Mathematical Programming, 46 (1990), 259.  doi: 10.1007/BF01585745.  Google Scholar

[15]

Dong-Won Kim, Dong-Gil Na and F. Frank Chen, Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective,, Robotics and Computer Integrated Manufacturing, 19 (2003), 173.   Google Scholar

[16]

Antoon W. J. Kolen and Leo G. Kroon, On the computational complexity of (maximum) class scheduling,, European Journal of Operational Research, 54 (2003), 23.   Google Scholar

[17]

Lawler and Labetoulle, On preemtive scheduling of unrelated parallel processors by linear programming,, Journal of the Association for Computing Machinery, 25 (1978), 621.  doi: 10.1145/322092.322101.  Google Scholar

[18]

Kai Li and Shan-lin Yang, Non-identical parallel-machine scheduling research with minimizing total weighted completion times: Model, relaxations and algorithms,, Applied mathematical Modelling, 33 (2009), 2145.  doi: 10.1016/j.apm.2008.05.019.  Google Scholar

[19]

E. Mokotoff and J. L. Jimeno, Heuristic based on partial enumeration for the unrelated parallel processor scheduling problem,, Annals of Operations Research, 117 (2002), 133.  doi: 10.1023/A:1021569406280.  Google Scholar

[20]

Silvano Martello, Francois Soumis and Paolo Toth, Exact and approximation algorithms for makespan minimization on unrelated parallel machine,, Discrete Applied Mathematics, 75 (1997), 169.  doi: 10.1016/S0166-218X(96)00087-X.  Google Scholar

[21]

C. N. Potts, Analysis of a linear programming heuristic for scheduling unrelated parallel machines,, Discrete Applied Mathematics, 10 (1985), 155.  doi: 10.1016/0166-218X(85)90009-5.  Google Scholar

[22]

David B. Shmoys and Eva Tardos, An approximation algorithm for the generalized assignment problem,, Mathematical Programming, 62 (1993), 461.  doi: 10.1007/BF01585178.  Google Scholar

[23]

B. Srivastava, An effective heuristic for minimizing makespan on unrelated parallel processor,, Journal of the Operational Research Society, 49 (1998), 886.   Google Scholar

[24]

Yongzhong Wu and Ping Ji, A scheduling problem for PCB assembly: a case with multiple line,, International Journal Advanced Technology, 43 (2009), 1189.   Google Scholar

[25]

L. Yu, H. M. Shih, M. Pfund, W. M. Carlyle and J. W. Fowler, Scheduling of unrelated parallel machines: an application to PWB manufacturing,, IIE Transactions, 34 (2002), 921.   Google Scholar

[26]

Vassilis E. Zafeiris and E. A. Giakoumakis, Towards flow scheduling optimization in multihomed mobile host,, IEEE 19th International Symposium of Personal, (2008), 1.   Google Scholar

show all references

References:
[1]

Ali Allahverdi, C. T. Ng, T. C. E. Cheng and Mikhail Y. Kovalyov, A survey of scheduling problems with setup times or costs,, European Journal of Operational Research, 187 (2008), 985.  doi: 10.1016/j.ejor.2006.06.060.  Google Scholar

[2]

Georgios C. Anagnostopoulos and Ghaith Rabadi, A simulated annealing algorithm for the unrelated parallel machine scheduling problem,, Proceedings of the 5th Biannual world automation congress, 14 (2002), 115.   Google Scholar

[3]

Bjorn Andersson, Static-priority Scheduling on Multiprocessors,, Ph. D thesis, (2003).   Google Scholar

[4]

V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy and Aravind Srivivasan, Scheduling on unrelated machines under tree-like precedence constraints,, Algorithmica, 55 (2005), 205.  doi: 10.1007/s00453-007-9004-y.  Google Scholar

[5]

Jacek Blazewicz, Moshe Dror and Jan Weglarz, Mathematical programming formulations for machine scheduling : A survey,, European Journal of Operational Research, 51 (1991), 283.   Google Scholar

[6]

Bo Chen, Chris N. Potts and Gerhard J. Woeginger, A review of machine scheduling: Complexity, algorithms and approximability,, in Handbook of Combinatorial Optimization (Vol. 3) (eds. D.-Z. Du and P. M. Pardalos), (1998), 21.   Google Scholar

[7]

M. Ghirardi and C. N. Potts, Makespan minimization for scheduling unrelated parallel machines: A recovering beam search approach,, European Journal of Operational Research, 165 (2005), 457.   Google Scholar

[8]

C. A. Glass, C. N. Potts and P. Shade, Unrelated parallel machine scheduling using local search,, Mathematical and Computer Modelling, 20 (1994), 41.   Google Scholar

[9]

Valery Gordon, Jean-Marie Proth and Chengbin Chu, A survey of the state-of-the-art of common due date assignement and scheduling research,, European Journal of Operational Research, 139 (2002), 1.  doi: 10.1016/S0377-2217(01)00181-3.  Google Scholar

[10]

R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey,, Annals of Discrete Mathematics, 5 (1979), 287.   Google Scholar

[11]

Alexander Grigoriev, Maxim Sviridenko and Marc Uetz, Unrelated parallel machine scheduling with resource dependent processing times,, Lecture Notes in Computer Science, (2005), 182.  doi: 10.1007/11496915_14.  Google Scholar

[12]

Jeffrey Herrmann, Jean-Marie Proth and Nathalie Sauer, Heuristic for unrelated machine scheduling with presedence canstraint,, European Journal of Operational Research, 102 (1997), 528.   Google Scholar

[13]

Han Hoogeveen, Martin Skutella and Gerhard J. Woeginger, Mathematical Programming,, European Journal of Operational Research, 94 (2003), 361.  doi: 10.1007/s10107-002-0324-z.  Google Scholar

[14]

Jan Karel Lenstra, David B Shmoys and Eva Tardos, Approximation algorithms for scheduling unrelated parallel machine,, Mathematical Programming, 46 (1990), 259.  doi: 10.1007/BF01585745.  Google Scholar

[15]

Dong-Won Kim, Dong-Gil Na and F. Frank Chen, Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective,, Robotics and Computer Integrated Manufacturing, 19 (2003), 173.   Google Scholar

[16]

Antoon W. J. Kolen and Leo G. Kroon, On the computational complexity of (maximum) class scheduling,, European Journal of Operational Research, 54 (2003), 23.   Google Scholar

[17]

Lawler and Labetoulle, On preemtive scheduling of unrelated parallel processors by linear programming,, Journal of the Association for Computing Machinery, 25 (1978), 621.  doi: 10.1145/322092.322101.  Google Scholar

[18]

Kai Li and Shan-lin Yang, Non-identical parallel-machine scheduling research with minimizing total weighted completion times: Model, relaxations and algorithms,, Applied mathematical Modelling, 33 (2009), 2145.  doi: 10.1016/j.apm.2008.05.019.  Google Scholar

[19]

E. Mokotoff and J. L. Jimeno, Heuristic based on partial enumeration for the unrelated parallel processor scheduling problem,, Annals of Operations Research, 117 (2002), 133.  doi: 10.1023/A:1021569406280.  Google Scholar

[20]

Silvano Martello, Francois Soumis and Paolo Toth, Exact and approximation algorithms for makespan minimization on unrelated parallel machine,, Discrete Applied Mathematics, 75 (1997), 169.  doi: 10.1016/S0166-218X(96)00087-X.  Google Scholar

[21]

C. N. Potts, Analysis of a linear programming heuristic for scheduling unrelated parallel machines,, Discrete Applied Mathematics, 10 (1985), 155.  doi: 10.1016/0166-218X(85)90009-5.  Google Scholar

[22]

David B. Shmoys and Eva Tardos, An approximation algorithm for the generalized assignment problem,, Mathematical Programming, 62 (1993), 461.  doi: 10.1007/BF01585178.  Google Scholar

[23]

B. Srivastava, An effective heuristic for minimizing makespan on unrelated parallel processor,, Journal of the Operational Research Society, 49 (1998), 886.   Google Scholar

[24]

Yongzhong Wu and Ping Ji, A scheduling problem for PCB assembly: a case with multiple line,, International Journal Advanced Technology, 43 (2009), 1189.   Google Scholar

[25]

L. Yu, H. M. Shih, M. Pfund, W. M. Carlyle and J. W. Fowler, Scheduling of unrelated parallel machines: an application to PWB manufacturing,, IIE Transactions, 34 (2002), 921.   Google Scholar

[26]

Vassilis E. Zafeiris and E. A. Giakoumakis, Towards flow scheduling optimization in multihomed mobile host,, IEEE 19th International Symposium of Personal, (2008), 1.   Google Scholar

[1]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168

[2]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340

[3]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[4]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444

[5]

Huiying Fan, Tao Ma. Parabolic equations involving Laguerre operators and weighted mixed-norm estimates. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5487-5508. doi: 10.3934/cpaa.2020249

[6]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051

[7]

Jie Zhang, Yuping Duan, Yue Lu, Michael K. Ng, Huibin Chang. Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020071

[8]

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251

[9]

Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253

[10]

Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020384

[11]

Ahmad Z. Fino, Wenhui Chen. A global existence result for two-dimensional semilinear strongly damped wave equation with mixed nonlinearity in an exterior domain. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5387-5411. doi: 10.3934/cpaa.2020243

[12]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321

[13]

Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045

[14]

Adel M. Al-Mahdi, Mohammad M. Al-Gharabli, Salim A. Messaoudi. New general decay result for a system of viscoelastic wave equations with past history. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020273

[15]

Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020453

[16]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[17]

Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of a Sobolev type impulsive functional evolution system in Banach spaces. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020049

[18]

Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075

[19]

Helmut Abels, Andreas Marquardt. On a linearized Mullins-Sekerka/Stokes system for two-phase flows. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020467

[20]

Yichen Zhang, Meiqiang Feng. A coupled $ p $-Laplacian elliptic system: Existence, uniqueness and asymptotic behavior. Electronic Research Archive, 2020, 28 (4) : 1419-1438. doi: 10.3934/era.2020075

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]