The Unrelated Parallel Machine Scheduling with a Dependent Time Setup using Ant Colony Optimization Algorithm


  • Farida Pulansari University of Pembangunan National "Veteran" Jawa Timur
  • Triyono Dwi Retno M. University of Pembangunan National "Veteran" Jawa Timur



Ant Colony Optimization (ACO), Makespan, Tardiness, Paralel Machine Scheduling (PMS).


The unrelated parallel machine scheduling (PMS) problem is essential for the manufacturing industry. Scheduling will save company resources, especially time management. By solving scheduling problems quickly and precisely, the company can get more profit. On that note, this paper focused on unrelated PMS problems, which did not consider the inherent uncertainty in processing time and set up time by minimizing the makespan and tardiness. This paper aimed to minimize the makespan and tardiness using timing considerations. This paper described how to schedule unrelated parallel machines using the Ant Colony Optimization (ACO) Algorithm approach. The ACO is beneficial for inherent parallelism problems and can provide fast and reasonable solutions. This study revealed that the results of ACO Algorithm scheduling were obtained under a steady condition in iteration 30467. This condition can be interpreted that the makespan and tardiness value is close to 2.75%. By minimizing the makespan and tardiness, the delay of product delivery to consumers can be anticipated. Moreover, a company can maintain customer satisfaction and increase its profit.


Huang, M., Huang, R., Sun, B., and Li , L., Research on the Production Scheduling Optimization for Virtual Enterprises, Mathematical Problems in Engineering 2013, 2013, pp. 1–9.

Pinedo, M.L., Scheduling Theory, Algorithms, and Systems, 5th ed., Springer, New York, 2016

Sasikala, B., and Eswaramurthy, V.P., Ant Colony Optimization for Job Shop Scheduling Problem, Proceeding of 8th IASTED International Conference On Artificial Intelligence and Soft Computing (ASC 2004) 3(February), 2017, pp. 451–152

Torabi, S.A., Sahebjamnia, N., Mansouri, S.A., and Aramon Bajestani, M., A Particle Swarm Opti¬mization for a Fuzzy Multi-objective Unrelated Parallel Machines Scheduling problem, Applied Soft Computing Journal 13, 2013, pp. 4750–4762

Lin, Y.K., Particle Swarm Optimization Algorithm for Unrelated Parallel Machine Scheduling with Release Dates, Mathematical Problems in Engineering 2013, 2013

Arnaout, J.P., Musa, R., and Rabadi, G., Ant Colony Optimization Algorithm to Parallel Machine Scheduling Problem with Setups, 4th IEEE Conference on Automation Science and Engineering, CASE 2008, 2008

Low, C., and Wu, G.H., Unrelated Parallel-Machine Scheduling with Controllable Processing Times and Eligibility Constraints to Minimize the Makespan, Journal of Industrial and Production Engineering 33(4), 2016, pp. 286–293

Jia, Z., Yan, J., Leung, J.Y.T., Li, K., and Chen, H., Ant Colony Optimization Algorithm for Scheduling Jobs with Fuzzy Processing Time on Parallel Batch Machines with Different Capacities, Applied Soft Computing 75, 2019, pp. 548–561

Chen, S., and Wang, L., ACO-based Parallel Machine Scheduling Considering Both Setup Time and Run-based Preventive Maintenance with Reliability Constraints, IEEE International Conference on Industrial Engineering and Engineering Management, IEEE Computer Society (2019), 227–231

Gagné, C., Gravel, M., and Price, W., Scheduling a Single Machine where Setup Times are Sequence Dependent using an Ant-colony Heu¬ristic, Abstract Proceedings of ANTS’2000 (October), 2000, pp. 157–160

Song, H., Yi, S., Liu, M., and Qin, G., Single Machine Scheduling Based on EDD-SDST-ACO Heuristic Algorithm, Journal of Intelligent Systems 26(4), 2017, pp. 657–667

Jia, Z. hong, Pei, M. li, and Leung, J.Y.T., Multi-objective ACO Algorithms to Minimise the Makespan and the Total Rejection Cost on BPMs with Arbitrary Job Weights, International Jour-nal of Systems Science 48(16), 2017, pp. 3542–3557

Li, H., Gajpal, Y., and Bector, C.R., Single Machine Scheduling with Two-agent for Total Weighted Completion Time Objectives, Applied Soft Computing Journal 70, 2018, pp. 147–156

Huang, R.H., and Yu, S.C., Two-stage Multiprocessor Flow Shop Scheduling with Deteriorating Maintenance in Cleaner Production, Journal of Cleaner Production 135, 2016, pp. 276–28

Qin, W., Zhang, J., and Song, D., An Improved Ant Colony Algorithm for Dynamic Hybrid Flow Shop Scheduling with Uncertain Processing Time, Journal of Intelligent Manufacturing 29(4), 2018, pp. 891–904

Huang, R.H., Yang, C.L., and Cheng, W.C., Flexible Job Shop Scheduling with Due Window - A Two-pheromone Ant Colony Approach, International Journal of Production Economics 141(2), 2013, pp. 685–697

Khan, S.A., Alam, M.A., and Umer, M., Resource Optimization in Job-shop Scheduling using Ant-Colony-Optimization Metaheuristic, Proceedings of the Pakistan Academy of Sciences: Part A 53(2A), 2016, pp. 131–144

El Khoukhi, F., Boukachour, J., and El Hilali Alaoui, A., The ‘Dual-Ants Colony’: A Novel Hybrid approach for the Flexible Job Shop Sche-duling Problem with Preventive Maintenance, Computers and Industrial Engineering 106, 2017, pp. 236–255

Wang, L., Cai, J., Li, M., and Liu, Z., Flexible Job Shop Scheduling Problem Using an Improved Ant Colony Optimization, Scientific Program-ming 2017, 2017

Neto, R.F.T, Godinho Filho, M., and da Silva, F.M., An Ant Colony Optimization Approach for the Parallel Machine Scheduling Problem with Outsourcing Allowed, Journal of Intelligent Manufacturing 26(3), 2015, pp. 527–538

Öztürkoğlu, Ö., Identical Parallel Machine Scheduling with Nonlinear Deterioration and Multiple Rate Modifying Activities, An International Journal of Optimization and Control: Theories & Applications (IJOCTA) 7(2), 2017, pp. 167

Arnaout, Jean-Paul., Rabadi, Ghaith., and Musa, Rami., A Two-stage Ant Colony Optimization Algorithm to Minimize the Makespan on Unrelated Parallel Machines with Sequence-Dependent Setup Times, Journal of Intelligent Manufacturing, 21(6), 2010, pp. 693-701.

Jia, Z., Yan, J., Leung, J. Y. T., Li, K., and Chen, H., Ant Colony Optimization Algorithm for Scheduling Jobs with Fuzzy Processing Time on Parallel Batch Machines with Different Capacities, Applied Soft Computing Journal, 75, pp.548-561.

Guinet, A., Scheduling Sequence-dependent Jobs on Identical Parallel Machines to Minimize Completion Time Criteria, International Journal of Production Research 31(7), 1993, pp. 1579–1594

Wang, L., Wang, S., and Zheng, X., A Hybrid Estimation of Distribution Algorithm for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times, 2016

Santos, L.P. dos, Vieira, G.E., Leite, H.V. dos R., and Steiner, Maria Teresinha Arns, Ant Colony Optimisation for Backward Production Scheduling, Advances in Artificial Intelligence 2012(i), 2012, pp. 1–12.

Dorigo, M., Maniezzo, V., and Colorni, A., Ant System: Optimization by a Colony of Cooperating Agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics 26(1), 1996, pp.29–41.