1. Home
  2. Issues
  3. Volume 29, Issue 2 (2018)
  4. Single-Machine and Parallel-Machine Para ...

Informatica


Single-Machine and Parallel-Machine Parallel-Batching Scheduling Considering Deteriorating Jobs, Various Group, and Time-Dependent Setup Time
Volume 29, Issue 2 (2018), pp. 281–301
Pub. online: 1 January 2018      Type: Research Article      Open accessOpen Access
Received
1 May 2017
Accepted
1 February 2018
Published
1 January 2018

Abstract

This paper studies a set of novel integrated scheduling problems by taking into account the combinatorial features of various groups, parallel-batching, deteriorating jobs, and time-dependent setup time simultaneously under the settings of both single-machine and parallel-machine, and the objective of the studied problems is to minimize the makespan. In order to solve the single-machine scheduling problem, we first investigate the structural properties on jobs sequencing, jobs batching, and batches sequencing for the optimal solution, and then develop a scheduling rule. Moreover, for solving the parallel-machine scheduling problem, we exploit the optimal structural properties and batching rule, and propose a novel hybrid AIS-VNS algorithm incorporating Artificial Immune System algorithm (AIS) and Variable Neighbourhood Search (VNS). Extensive computational experiments are conducted to evaluate the performance of the proposed AIS-VNS algorithm, and comparison results show that the proposed algorithm performs quite well in terms of both efficiency and solution quality.

References

 
Abedi, M., Seidgar, H., Fazlollahtabar, H., Bijani, R. (2015). Bi-objective optimisation for scheduling the identical parallel batch-processing machines with arbitrary job sizes, unequal job release times and capacity limits. International International Journal of Production Research, 53(6), 1680–1711.
 
Arroyo, J.E.C., Leung, J.Y.-T. (2017). An effective iterated greedy algorithm for scheduling unrelated parallel batch machines with non-identical capacities and unequal ready times. Computers and Industrial Engineering, 105, 84–100.
 
Bai, J., Li, Z.-R., Wang, J.-J., Huang, X. (2014). Single machine common flow allowance scheduling with deteriorating jobs and a rate-modifying activity. Applied Mathematical Modelling, 38(23), 5431–5438.
 
Castro, L.R.D., Timmis, J.L. (2002). Artificial Immune Systems: A New Computational Intelligence Paradigm. Springer-Verlag, New York. Inc.
 
Castro, L.N.D., Zuben, F.J.V. (2000). Artificial Immune Systems: Part II – A Survey of Applications. Technical Report.
 
Cheng, T.C.E., Ding, Q. (2000). Single machine serial-batching scheduling with independent setup time and deteriorating job processing times. Acta Informatica, 36, 673–692.
 
Cheng, T.C.E., Ding, Q., Lin, B.M.T. (2004). A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research, 152(1), 1–13.
 
Duarte, A., Pantrigo, J.J., Pardo, E.G., Mladenovic, N. (2015). Multi-objective variable neighborhood search: an application to combinatorial optimization problems. Journal of Global Optimization, 63(3), 515–536.
 
Ercan, M.F. (2008). A performance comparison of PSO and GA in scheduling hybrid flow-shops with multiprocessor tasks. In: ACM Symposium on Applied Computing. DBLP, pp. 1767–1771.
 
Fan, B., Yuan, J., Li, S. (2012). Bi-criteria scheduling on a single parallel-batch machine. Applied Mathematical Modelling, 36(3), 1338–1346.
 
Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. (1979). Optimization and approximation indeterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287–326.
 
Ham, A. (2017). Flexible job shop scheduling problem for parallel batch processing machine with compatible job families. Applied Mathematical Modelling, 45. https://doi.org/10.1016/j.apm.2016.12.034.
 
Hansen, P., Mladenović, N. (2001). Variable neighborhood search: principles and applications. European Journal of Operational Research, 130(3), 449–467.
 
Hashemipour, M.S., Soleimani, S.A. (2016). Artificial immune system based on adaptive clonal selection for feature selection and parameters optimisation of support vector machines. Connection Science, 1, 1–16.
 
Hazir, Ö., Kedad-Sidhoum, S. (2014). Batch sizing and just-in-time scheduling with common due date. Annals of Operations Research, 213(1), 187–202.
 
He, C., Leung, J.Y.T., Lee, K., Pinedo, M.L. (2016). Scheduling a single machine with parallel batching to minimize makespan and total rejection cost. Discrete Applied Mathematics, 2016(204), 150–163.
 
Jia, Z.-H., Leung, J.Y.-T. (2015). A meta-heuristic to minimize makespan for parallel batch Machines with arbitrary job sizes. European Journal of Operational Research, 240, 649–665.
 
Jia, Z.-H., Li, K., Leung, J.Y.-T. (2015). Single machine scheduling with deadlines and increasing rates of processing times. International Journal of Production Economics, 169, 1–10.
 
Komaki, G.M., Mobin, S., Teymourian, E., Sheikh, S. (2015). A general variable neighborhood search algorithm to minimize makespan of the distributed permutation flowshop scheduling problem. International Journal of Social, Behavioral, Educational, Economic, Business and Industrial Engineering, 9(8), 2618–2625.
 
Lalla-Ruiz, E., Voß (2016). Modeling the parallel machine scheduling Problem with step deteriorating jobs. European Journal of Operational Research, 255(1), 21–33.
 
Lei, D. (2015). Variable neighborhood search for two-agent flow shop scheduling problem. Computers & Industrial Engineering, 80(C), 125–131.
 
Lenstra, J.K., Rinnooy, A.H.G., Brucker, P. (1977). Complexity of Machine Scheduling Problems. Journal of Scheduling, 1, 343–362.
 
Li, W., Yuan, J. (2014). Improved online algorithms for the batch scheduling of equal-length jobs with incompatible families to maximize the weighted number of early jobs. Optimization Letters, 8(5), 1691–1706.
 
Li, S., Ng, C.T., Cheng, T.C.E., Yuan, J. (2007). Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan. European Journal of Operational Research, 210, 482–488.
 
Li, X., Ishii, H., Chen, M. (2015). Single machine parallel-batching scheduling problem with fuzzy due-date and fuzzy precedence relation. International Journal of Production Research, 53(9), 2707–2717.
 
Li, W., Li, S., Feng, Q. (2017). Online batch scheduling with kind release times and incompatible families to minimize makespan. Optimization Letters, 8(5). https://doi.org/10.1007/s11590-017-1113-1.
 
Liu, L.L., Ng, C.T., Cheng, T.C.E. (2014). Scheduling jobs with release dates on parallel batch processing machines to minimize the makespan. Optimization Letters, 8(1), 307–318.
 
Liu, X., Lu, S., Pei, J., Pandalos, P.M. (2017). A hybrid VNS-HS algorithm for a supply chain scheduling problem with deteriorating jobs. International Journal of Production Research, 1–18.
 
Lu, Y.-Y. (2016). Research on no-idle permutation flowshop scheduling with time-dependent learning effect and deteriorating jobs. Applied Mathematical Modelling, 40(4), 3447–3450.
 
Mladenović, N., Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11), 1097–1100.
 
Ozturk, O., Begen, M.A., Zaric, G.S. (2017). A branch and bound algorithm for scheduling unit size jobs on parallel batching machines to minimize makespan. International Journal of Production Research, 55(6), 1815–1831.
 
Panigrahi, B.K., Yadav, S.R., Agrawal, S., Tiwari, M.K. (2007). A clonal algorithm to solve economic load dispatch. Electric Power Systems Research, 77(10), 1381–1389.
 
Pei, J., Pardalos, P.M., Liu, X., Fan, W., Yang, S. (2015a). Serial batching scheduling of deteriorating jobs in a two-stage supply chain to minimize the makespan. European Journal of Operational Research, 244(1), 13–25.
 
Pei, J., Liu, X., Pardalos, P.M., Fan, W., Yang, S. (2015b). Single machine serial-batching scheduling with independent setup time and deteriorating job processing times. Optimization Letters, 9(1), 91–104.
 
Pei, J., Liu, X., Pardalos, P.M., Fan, W., Yang, S. (2017a). Scheduling deteriorating jobs on a single serial-batching machine with multiple job types and sequence-dependent setup times. Annals of Operations Research, 249, 175–195.
 
Pei, J., Liu, X., Pardalos, P.M., Migdalas, A., Yang, S. (2017b). Serial-batching scheduling with time-dependent setup time and effects of deterioration and learning on a single-machine. Journal of Global Optimization, 67(1), 251–262.
 
Pei, J., Liu, X., Fan, W., Pardalos, P.M., Lu, S. (2017c). A hybrid BA-VNS algorithm for coordinated serial-batching scheduling with deteriorating jobs, financial budget, and resource constraint in multiple manufacturers. Omega. https://doi.org/10.1016/j.omega.2017c.12.003.
 
Su, L.-H., Wang, H.-M. (2017). Minimizing total absolute deviation of job completion times on a single machine with cleaning activities. Computers and Industrial Engineering, 103, 242–249.
 
Tang, L., Gong, H. (2009). The coordination of transportation and batching scheduling. Applied Mathematical Modelling, 33(10), 3854–3862.
 
Tang, L., Liu, P. (2009). Two-machine flowshop scheduling problems involving a batching machine with transportation or deterioration consideration. Applied Mathematical Modelling, 33(2), 1187–1199.
 
Tang, L., Zhao, X., Liu, J., Leung, J.Y.T. (2017). Competitive two-agent scheduling with deteriorating jobs on a single parallel-batching machine. European Journal of Operational Research, 263(2), 401–411.
 
Wang, X.-Y., Wang, J.-J. (2014). Scheduling deteriorating jobs with a learning effect on unrelated parallel machines. Applied Mathematical Modelling, 38(21–22), 5231–5238.
 
Wang, X., Tang, L. (2008). Integration of batching and scheduling for hot rolling production in the steel industry. International Journal of Advanced Manufacturing Technology, 36(5), 431–441.
 
Wang, J.B., Li, L. (2017). Machine scheduling with deteriorating jobs and modifying maintenance activities. The Computer Journal, 1–7.
 
Wen, Xu H, Y., Yang, J. (2011). A heuristic-based hybrid genetic-variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system. Information Sciences, 181(3), 567–581.
 
Xuan, H., Tang, L. (2007). Scheduling a hybrid flowshop with batch production at the last stage. Computers and Operations Research, 34(9), 2718–2733.
 
Yang, S.-W., Wan, L., Yin, N. (2015). Research on single machine SLK/DIF due window assignment problem with learning effect and deteriorating jobs. Applied Mathematical Modelling, 39(15), 4593–4598.
 
Yin, Y., Wang, Y., Cheng, T.C.E., Liu, W., Li, J. (2017). Parallel-machine scheduling of deteriorating jobs with potential machine disruptions. Omega, 69, 17–28.
 
Ying, K.C., Lin, S.W. (2014). Efficient wafer sorting scheduling using a hybrid artificial immune system. Journal of the Operational Research Society, 65(2), 169–179.
 
Yue, Q., Wan, G. (2016). Single machine SLK/DIF due window assignment problem with job-dependent linear deterioration effects. Journal of the Operational Research Society, 67(6), 872–883.
 
Zhang, X., Wu, W.H., Lin, W.C., Wu, C.C. (2017). Machine scheduling problems under deteriorating effects and deteriorating rate-modifying activities. Journal of the Operational Research Society, 1–10.

Biographies

Liao Baoyu

B. Liao is currently working on his PhD degree at the School of Management, Hefei University of Technology. He obtained his master’s degrees from Hefei University of Technology in 2015. His research interests include supply chain scheduling and metaheuristics.

Pei Jun
feiyijun.ufl@gmail.com

J. Pei is currently an associate professor at the School of Management, Hefei University of Technology, Hefei, China. He is also the associate editor for Journal of Global Optimization (2018.1-Present), Optimization Letters (2016.8-Present), Energy Systems (2015.12-Present), Computational Social Networks (2016.7-Present) and a guest editor for Journal of Combinatorial Optimization. His research interests include supply chain scheduling, artificial intelligence, and information systems.

Yang Shanlin

S. Yang is a professor at School of Management, Hefei University of Technology, Hefei, China. He is a member of Chinese Academy of Engineering. He servers as the director of National & Local Joint Engineering Research Center for Intelligent Decision and Information Systems and the director of Key Laboratory of Process Optimization and Intelligent Decision-making. His research interests include decision science and technology, optimization theory and method, management information system.

Pardalos Panos M.

P.M. Pardalos serves as a distinguished professor of industrial and systems engineering at the University of Florida, Gainesville, FL, USA. He is also the director of the Center for Applied Optimization. Dr. Pardalos is a world leading expert in global and combinatorial optimization. His recent research interests include network design problems, optimization in telecommunications, e-commerce, data mining, biomedical applications, and massive computing.

Lu Shaojun

S. Lu is currently working on his PhD degree at the School of Management, Hefei University of Technology. He obtained his BS degrees from Hefei University of Technology in 2015. His research interests include supply chain scheduling and metaheuristics.


Full article Related articles Cited by PDF XML
Full article Related articles Cited by PDF XML

Copyright
© 2018 Vilnius University
Open access article under the CC BY license.

Keywords
scheduling parallel-batching group scheduling deterioration time-dependent setup time

Metrics
since January 2020
1306

Article info
views

849

Full article
views

627

PDF
downloads

248

XML
downloads


Share


RSS