The Unrelated Parallel Machine Scheduling with a Dependent Time Setup using Ant Colony Optimization Algorithm
Keywords: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.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).