Unrelated parallel machine scheduling with processing constraints and sequence dependent setup times

Document Type : Research Paper

Authors

1 گروه مهندسی صنایع دانشگاه کردستان، سنندح، ایران

2 مهندسی صنایع دانشگاه کردستان، سنندح، ایران

Abstract

In real-world problems, machines are often not available for some periods of time due to events such as breakdowns, maintenance activities, and already planned operations. In this research, an unrelated parallel machine scheduling problem is considered where each machine is not available for some times during the planning horizon and also may not be capable of processing some jobs; these constraints are referred to as the processing constraints. On the other hand, the setup times are assumed to be job sequence-dependent as well as machine-dependent. The objective function of the problem considered is to minimize the total earliness and tardiness. First, the problem is formulated as a mixed integer linear programming model and then, in view of its NP-hardness, an imperialist competitive algorithm utilizing a new decoding procedure is proposed to solve large-sized problem instances. To assess the performance of the proposed algorithm, a number of instances are generated and solved.

Keywords

References

  1. Sun, K., and Li, H., (2010). “Scheduling Problems with Multiple Maintenance Activities and Non-Preemptive Jobs on Two Identical Parallel Machines”, International Journal of Production Economics, Vol. 124, No. 1, PP. 151–158.
  2. Zhao, C., Ji, M., and Tang, H. (2011). “Parallel-Machine Scheduling with an Availability Constraint”, Computers and Industrial Engineering, Vol. 61, No. 3, PP. 778–781.
  3. Tan, Z., Chen, Y., and Zhang, A. (2013). “On the Exact Bounds of SPT for Scheduling on Parallel Machines with Availability Constraints”, International Journal of Production Economics, Vol. 146, No. 1, PP. 293–299.
  4. Xu, D., and Yang, D. L. (2013). “Makespan Minimization for Two Parallel Machines Scheduling with a Periodic Availability Constraint: Mathematical Programming Model, Average-Case Analysis, and Anomalies”, Applied Mathematical Modelling, Vol. 37, No. 14, PP. 7561–7567.
  5. Wang, X., and Cheng, T. C. E. (2015). “A Heuristic for Scheduling Jobs on Two Identical Parallel Machines with a Machine Availability Constraint”, International Journal of Production Economics, Vol. 161, PP. 74–82.
  6. Lee, J. Y., and Kim, Y. D. (2015). “A Branch and Bound Algorithm to Minimize Total Tardiness of Jobs in a Two Identical-Parallel-Machine Scheduling Problem with a Machine Availability Constraint”, Journal of the Operational Research Society, Vol. 66, No. 9, PP. 1542–1554.
  7. He, J., Li, Q., and Xu, D. (2016). “Scheduling Two Parallel Machines with Machine-Dependent Availabilities”, Computers and Operations Research, Vol. 72, PP. 31–42.
  8. Lee, C. Y. (1991). “Parallel Machines Scheduling with Nonsimultaneous Machine Available Time”, Discrete Applied Mathematics, Vol. 30, No. 1, PP. 53–61.
  9. Lee, C. Y., and Chen, Z. L. (2000). “Scheduling Jobs and Maintenance Activities on Parallel Machines”, Naval Research Logistics, Vol. 47, No. 2, PP. 145–165.

10. Gharbi, A., and Haouari, M. (2005). “Optimal Parallel Machines Scheduling with Availability Constraints”, Discrete Applied Mathematics, Vol. 148, No. 1, PP. 63–87.

11. Sheen, G. J., Liao, L. W., and Lin, C. F. (2008). “Optimal Parallel Machines Scheduling with Machine Availability and Eligibility Constraints”, International Journal of Advanced Manufacturing Technology, Vol. 36, No. 1 and 2, PP. 132–139.

12. Shen, L., Wang, D., and Wang, X. Y. (2013). “Parallel-Machine Scheduling with Non-Simultaneous Machine Available Time”, Applied Mathematical Modelling, Vol. 37, No. 7, PP. 5227–5232.

13. Huo, Y., and Zhao, H. (2015). “Total Completion Time Minimization on Multiple Machines Subject to Machine Availability and Makespan Constraints”, European Journal of Operational Research, Vol. 243, No. 2, PP. 547–554.

14. Lee, W. C., Wang, J. Y., and Lee, L. Y. (2015). “A Hybrid Genetic Algorithm for an Identical Parallel-Machine Problem with Maintenance Activity”, Journal of the Operational Research Society, Vol. 66, No. 11, PP. 1906–1918.

15. Yin, Y., Wang, Y., Cheng, T. C. E., Liu, W., and Li, J. (2017). “Parallel-Machine Scheduling of Deteriorating Jobs with Potential Machine Disruptions”, Omega, Vol. 69, PP. 17–28.

16. Suresh V., and Ghaudhuri, D. (1996). “Scheduling of Unrelated Parallel Machines When Machine Availability Is Specified”, Production Planning and Control, Vol. 7, No. 4, PP. 393–400.

17. Baiazidi, M. (2014). “Group Scheduling Problem on Unrelated Parallel Machines with Availability Constraints and Sequence Dependent Setup Times”, Msc Thesis, University of Kurdistan.

18. Jiang, D., and Tan, J. (2016). “Scheduling with Job Rejection and Nonsimultaneous Machine Available Time on Unrelated Parallel Machines”, Theoretical Computer Science, Vol. 616, PP. 94–99.

19. Atashpaz-Gargari, E., and Lucas, C. (2007). “Imperialist Competitive Algorithm: An Algorithm for Optimization Inspired by Imperialistic Competition”, IEEE Congress on Evolutionary Computation, PP. 4661–4667.

20. Norouzi, N., Tavakkoli-Moghaddam, R., Sadegh-Amalnick, M., and Khaefi, S. (2015). “New Mathematical Modeling for a Facilities Location and Vehicle Routing Problem Solving by a Hybrid Imperialist Competitive Algorithm”, Journal of Industrial Engineering (University of Tehran), Vol. 49, No. 1, PP. 129–137.

21. Ahmadizar, F., and Farhadi, S. (2015). “Single-Machine Batch Delivery Scheduling with Job Release Dates, Due Windows and Earliness, Tardiness, Holding and Delivery Costs”, Computers and Operations Research, Vol. 53, PP. 194–205.

22. Fallah Sanami, S., Ramezanian, R., and Shafiei Nikabadi, M. (2016). “Simultaneous Lot-Sizing and Scheduling in Hybrid Flow Shop Production Environment with Resource Constraint”, Journal of Industrial Engineering (University of Tehran), Vol. 50, No. 2, PP. 295–310.

23. Yazdani, M., Aleti, A., Khalili, S. M., and Jolai, F. (2017). “Optimizing the Sum of Maximum Earliness and Tardiness of the Job Shop Scheduling Problem”, Computers and Industrial Engineering, Vol. 107, PP. 12–24.

24. Panahi, I., and Nahavandi, N. (2017). “An Efficient Imperialist Competitive Algorithm for Resource Constrained Project Scheduling Problem”, Journal of Industrial Engineering (University of Tehran), Vol. 51, No. 2, PP. 161–174.

25. Afzalirad, M., and Rezaeian, J. (2017). “A Realistic Variant of Bi-Objective Unrelated Parallel Machine Scheduling Problem: NSGA-II And MOACO Approaches”, Applied Soft Computing, Vol. 50, PP. 109–123.

26. Radhakrishnan, S., and Ventura, J. A. (2000). “Simulated Annealing for Parallel Machine Scheduling with Earliness-Tardiness Penalties and Sequence-Dependent Set-Up Times”, International Journal of Production Research, Vol. 38, No. 10, PP. 2233–2252.

Advances in Industrial Engineering
Volume 53, Issue 1
January 2019
Pages 495-507

Files

Share

How to cite

Statistics