• 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 and 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-1032. doi: 10.1016/j.ejor.2006.06.060.

[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-120.

[3]

Bjorn Andersson, Static-priority Scheduling on Multiprocessors, Ph. D thesis, Chalmers University of Technology in Goteborg, Sweden, 2003.

[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-226. doi: 10.1007/s00453-007-9004-y.

[5]

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

[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), Kluwer Academic Publishers, (1998), 21-169.

[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-467.

[8]

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

[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-25. doi: 10.1016/S0377-2217(01)00181-3.

[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-326.

[11]

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

[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-537.

[13]

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

[14]

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

[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-181.

[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-38.

[17]

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

[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-2158. doi: 10.1016/j.apm.2008.05.019.

[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-150. doi: 10.1023/A:1021569406280.

[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-188. doi: 10.1016/S0166-218X(96)00087-X.

[21]

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

[22]

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

[23]

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

[24]

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

[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-931.

[26]

Vassilis E. Zafeiris and E. A. Giakoumakis, Towards flow scheduling optimization in multihomed mobile host, IEEE 19th International Symposium of Personal, Indoor and Mobile Radio Communication (PIMRC), (2008), 1-5.

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-1032. doi: 10.1016/j.ejor.2006.06.060.

[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-120.

[3]

Bjorn Andersson, Static-priority Scheduling on Multiprocessors, Ph. D thesis, Chalmers University of Technology in Goteborg, Sweden, 2003.

[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-226. doi: 10.1007/s00453-007-9004-y.

[5]

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

[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), Kluwer Academic Publishers, (1998), 21-169.

[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-467.

[8]

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

[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-25. doi: 10.1016/S0377-2217(01)00181-3.

[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-326.

[11]

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

[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-537.

[13]

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

[14]

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

[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-181.

[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-38.

[17]

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

[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-2158. doi: 10.1016/j.apm.2008.05.019.

[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-150. doi: 10.1023/A:1021569406280.

[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-188. doi: 10.1016/S0166-218X(96)00087-X.

[21]

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

[22]

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

[23]

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

[24]

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

[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-931.

[26]

Vassilis E. Zafeiris and E. A. Giakoumakis, Towards flow scheduling optimization in multihomed mobile host, IEEE 19th International Symposium of Personal, Indoor and Mobile Radio Communication (PIMRC), (2008), 1-5.

[1]

Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial and Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259

[2]

Reza Alizadeh Foroutan, Javad Rezaeian, Milad Shafipour. Bi-objective unrelated parallel machines scheduling problem with worker allocation and sequence dependent setup times considering machine eligibility and precedence constraints. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021190

[3]

Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009

[4]

Wan Nor Ashikin Wan Ahmad Fatthi, Adibah Shuib, Rosma Mohd Dom. A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse. Journal of Industrial and Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431

[5]

Hongtruong Pham, Xiwen Lu. The inverse parallel machine scheduling problem with minimum total completion time. Journal of Industrial and Management Optimization, 2014, 10 (2) : 613-620. doi: 10.3934/jimo.2014.10.613

[6]

Alireza Goli, Taha Keshavarz. Just-in-time scheduling in identical parallel machine sequence-dependent group scheduling problem. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021124

[7]

Chengwen Jiao, Qi Feng. Research on the parallel–batch scheduling with linearly lookahead model. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3551-3558. doi: 10.3934/jimo.2020132

[8]

Min Ji, Xinna Ye, Fangyao Qian, T.C.E. Cheng, Yiwei Jiang. Parallel-machine scheduling in shared manufacturing. Journal of Industrial and Management Optimization, 2022, 18 (1) : 681-691. doi: 10.3934/jimo.2020174

[9]

Sherif I. Ammar, Alexander Zeifman, Yacov Satin, Ksenia Kiseleva, Victor Korolev. On limiting characteristics for a non-stationary two-processor heterogeneous system with catastrophes, server failures and repairs. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1057-1068. doi: 10.3934/jimo.2020011

[10]

Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks and Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783

[11]

Mahdi Roozbeh, Saman Babaie–Kafaki, Zohre Aminifard. Two penalized mixed–integer nonlinear programming approaches to tackle multicollinearity and outliers effects in linear regression models. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3475-3491. doi: 10.3934/jimo.2020128

[12]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027

[13]

Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391

[14]

Yanxing Cui, Chuanlong Wang, Ruiping Wen. On the convergence of generalized parallel multisplitting iterative methods for semidefinite linear systems. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 863-873. doi: 10.3934/naco.2012.2.863

[15]

Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial and Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041

[16]

Bin Zheng, Min Fan, Mengqi Liu, Shang-Chia Liu, Yunqiang Yin. Parallel-machine scheduling with potential disruption and positional-dependent processing times. Journal of Industrial and Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041

[17]

Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial and Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243

[18]

Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017

[19]

Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial and Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057

[20]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]