Abstract
This paper considers a fuzzy single batch-processing machine (SBPM) scheduling problem and aims to make it closer to a real-world application through a fuzzy set theory. For this purpose, jobs’ due dates are set to be fuzzy numbers and the membership function of a fuzzy due date assigned to each job represents the degree of satisfaction that a decision maker has with the completion time of that job. The objective is to maximize the total degree of satisfaction or equivalently to minimize the total degree of dissatisfaction over given jobs. Then, the fuzzy mathematical programming model is presented. To solve the model, we propose the imperialist competitive algorithm (ICA) and modify the assimilation policy (i.e., colonies moving) and imperialistic competition in order to overcome its immature convergence and improve its performances. Moreover, due to the significant role of parameters on the quality of random search algorithms, a robust calibration is applied on the parameters using the Taguchi optimization technique. To evaluate the proposed ICA, several random test problems are generated and its performance is compared to the traditional ICA, simulated annealing (SA), particle swarm optimization (PSO), genetic algorithm (GA), ant colony optimization (ACO), and earliest due date (EDD). The obtained computational results demonstrate the superiority and robustness of the modified ICA.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Atashpaz-Gargari E, Lucas C (2007) Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition. IEEE Congr Evol Comput 4661–4667
Behnamian J, Zandieh M (2011) A discrete colonial competitive algorithm for hybrid flowshop scheduling to minimize earliness and quadratic tardiness penalties. Expert Syst Appl 38:14490–14498
Bellanger A, Oulamara A (2010) Minimizing total completion time on a batching machine with job processing time compatibilities. Electron Notes Discrete Math 36:1295–1302
Bellman R, Zadeh L (1970) Decision-making in a fuzzy environment. Manag Sci 17:141–164
Bezdek JC (1993) Fuzzy models—what are they, and why? IEEE Trans Fuzzy Syst 1:1–9
Chang PC, Wang HM (2004) A heuristic for a batch processing machine scheduled to minimise total completion time with non-identical job sizes. Int J Adv Manuf Technol 24:615–620
Chen H, Du B, Huang GQ (2011) Scheduling a batch processing machine with non-identical job sizes: a clustering perspective. Int J Prod Res 49:5755–5778
Cheng B, Li K, Chen B (2010) Scheduling a single batch-processing machine with non-identical job sizes in fuzzy environment using an improved ant colony optimization. J Manuf Syst 29:29–34
Chou FD, Wang HM (2008) A scheduling for a single semiconductor batch-processing machine to minimize total weighted tardiness. J Chin Inst Ind Eng 25:136–147
Chou FD, Chang PC, Wang HM (2006) A hybrid genetic algorithm to minimize makespan for the single batch machine dynamic scheduling problem. Int J Adv Manuf Technol 31:350–359
Damodaran P, Manjeshwar PK, Srihari K (2006) Minimizing makespan on a batch processing machine with non-identical job sizes using genetic algorithms. Int J Prod Econ 103:882–891
Dupont L, Flipo CD (2002) Minimizing the makespan on a batch machine with nonidentical job sizes: an exact procedure. Comput Oper Res 29:807–819
Dupont L, Jolai Ghazvini F (1998) Minimizing makespan on a single batch processing machine with non-identical job sizes. Eur J Autom Syst 1998(32):431–440
Harikrishnan KK, Ishii H (2005) Single machine batch scheduling problem with resource dependent setup and processing time in the presence of fuzzy due date. Fuzzy Optim Decis Making 4:141–147
He CH, Lin Y, Yuan J (2007) Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan. Theor Comput Sci 381:234–240
Hochbaum DS, Landy D (1997) Scheduling semiconductor burn-in operations to minimize total flowtime. Oper Res 45:874–885
Husseinzadeh Kashan A, Karimi B (2008) Scheduling a single batch-processing machine with arbitrary job sizes and incompatible job families: an ant colony framework. J Oper Res Soc 59:1269–1280
Husseinzadeh Kashan A, Karimi B, Jolai F (2006) Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with nonidentical job sizes. Int J Prod Res 44:2337–2360
Husseinzadeh Kashan A, Karimi B, Jolai F (2010) An effective hybrid multi-objective genetic algorithm for bi-criteria scheduling on a single batch processing machine with non-identical job sizes. Eng Appl Artif Intell 23:911–922
Ikura Y, Gimple M (1986) Efficient scheduling algorithms for a single batch processing machine. Oper Res Lett 5:61–65
Ishii H, Tada M, Masuda T (1992) Two scheduling problems with fuzzy due-dates. Fuzzy Sets Syst 46:339–347
Jolai Ghazvini F (2005) Minimizing number of tardy jobs on a batch processing machine with incompatible job families. Eur J Oper Res 162:184–190
Jolai Ghazvini F, Dupont L (1998) Minimizing mean flow times criteria on a single batch processing machine with non-identical job sizes. Int J Prod Econ 55:273–280
Knutson K, Kempf K, Fowler J, Carlyle M (1999) Lot to order matching for a semiconductor assemble and test facility. IIE Trans 31:1103–1111
Koh SG, Koo PH, Kim DC, Hur WS (2005) Scheduling a single batch processing machine with arbitrary job sizes and incompatible job families. Int J Prod Econ 98:81–96
Kurz ME, Mason SJ (2008) Minimizing total weighted tardiness on a batch-processing machine with incompatible job families and job ready times. Int J Prod Res 46:131–151
Lee CY, Uzsoy R (1999) Minimizing makespan on a single batch processing machine with dynamic job arrivals. Int J Prod Res 37:219–236
Lee CY, Uzsoy R, Martin-Vega LA (1992) Efficient algorithms for scheduling semiconductor burn-in operations. Oper Res 40:764–775
Li C, Lee C (1997) Scheduling with agreeable release times and due dates on a batch processing machine. Eur J Oper Res 96:564–569
Liu LL, Ng CT, Cheng TCE (2007) Scheduling jobs with agreeable processing times and due dates on a single batch processing machine. Theor Comput Sci 374:159–169
Liu LL, Ng CT, Cheng TCE (2010) On the complexity of bicriteria scheduling on a single batch processing machine. J Sched 13:629–638
Mathirajan M, Sivakumar AI (2006) Minimizing total weighted tardiness on heterogeneous batch processing machines with incompatible job families. Int J Adv Manuf Technol 28:1038–1047
Mathirajan M, Sivakumar AI (2006) A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor. Int J Adv Manuf Technol 29:990–1001
Mathirajan M, Bhargav V, Ramachandran V (2010) Minimizing total weighted tardiness on a batch-processing machine with non-agreeable release times and due dates. Int J Adv Manuf Technol 48:1133–1148
Melouk S, Damodaran P, Chang PY (2004) Minimizing makespan for single batch processing machine with non-identical job sizes using simulated annealing. Int J Prod Econ 87:141–147
Molla-Alizadeh-Zavardehi S, Hajiaghaei-Keshteli M, Tavakkoli-Moghaddam R (2011) Solving a capacitated fixed-charge transportation problem by artificial immune and genetic algorithms with a Prüfer number representation. Expert Syst Appl 38:10462–10474
Mönch L, Unbehaun R, Choung YI (2006) Minimizing earliness–tardiness on a single burn-in oven with a common due date and maximum allowable tardiness constraint. OR Spect 28:177–198
Park SH (1995) Robust design and analysis for quality engineering. Chapman & Hall, London
Perez IC, Fowler JW, Carlyle WM (2005) Minimizing total weighted tardiness on a single batch process machine with incompatible job families. Comput Oper Res 32:327–341
Potts CN, Kovalyov MY (2000) Scheduling with batching: a review. Eur J Oper Res 120:228–249
RafieeParsa N, Husseinzadeh Kashan A, Karimi B (2010) A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes. Comput Oper Res 37:1720–1730
Rajabioun R, Atashpaz-Gargari E, Lucas C (2008) Colonial competitive algorithm as a tool for Nash equilibrium point achievement. Lect Notes Comput Sci 5073:680–695
Rajabioun R, Hashemzadeh F, Atashpaz-Gargari E, Mesgari B, Rajaei Salmasi F (2008b) Identification of a MIMO evaporator and its decentralized PID controller tuning using colonial competitive algorithm (pp. 11–12).IFAC World Congress
Sabouni MTY, Jolai F (2010) Optimal methods for batch processing problem with makespan and maximum lateness objectives. Appl Math Model 34:314–324
Sevaux M, Peres SD (2003) Genetic algorithms to minimize the weighted number of late jobs on a single machine. Eur J Oper Res 151:296–306
Sung CS, Choung YI (2000) Minimizing makespan on a single burn-in oven in semiconductor manufacturing. Eur J Oper Res 120:559–574
Sung CS, Choung YI, Hong JM, Kim YH (2002) Minimizing makespan on a single burn-in oven with job families and dynamic job arrivals. Comput Oper Res 29:995–1007
Tangudu SK, Kurz ME (2006) A branch and bound algorithm to minimise total weighted tardiness on a single batch processing machine with ready times and incompatible job families. Prod Plan Control 17:728–741
Tavakkoli-Moghaddam R, Rahimi-Vahed A, Mirzaei AH (2007) A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: weighted mean completion time and weighted mean tardiness. Inf Sci 177:5072–5090
Uzsoy R (1994) Scheduling a single batch-processing machine with non-identical job sizes. Int J Prod Res 32:1615–1635
Uzsoy R (1995) Scheduling batch processing machines with incompatible job families. Int J Prod Res 33:2685–2708
Uzsoy R, Yang Y (1997) Minimizing total weighted completion time on a single batch processing machine. Prod Oper Manag 6:57–73
Uzsoy R, Lee C, Martin-Vega L (1992) A review of production planning and scheduling models in the semiconductor industry, part I: system characteristics, performance evaluation and production planning. IIE Trans 24:47–60
Uzsoy R, Lee C, Martin-Vega L (1994) A review of prod planning and scheduling models in the semiconductor industry, part II: shop floor control. IIE Trans 26:44–55
Wang J (2004) A fuzzy robust scheduling approach for product development projects. Eur J Oper Res 152:180–194
Wang HM (2011) Solving single batch-processing machine problems using an iterated heuristic. Int J Prod Res 49:4245–4261
Wang CS, Uzsoy R (2002) A genetic algorithm to minimize maximum lateness on a batch processing machine. Comput Oper Res 29:1621–1640
Wang HM, Chang PC, Chou FD (2007) A hybrid forward/backward approach for single batch scheduling problems with non-identical job sizes. J Chin Inst Ind Eng 24:191–199
Yao S, Jiang Z, Li N (2012) A branch and bound algorithm for minimizing total completion time on a single batch machine within compatible job families and dynamic arrivals. Comput Oper Res 39:939–951
Yimer AD, Demirli K (2009) Fuzzy scheduling of job orders in a two-stage flowshop with batch-processing machines. Int J Approx Reason 50:117–137
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Molla-Alizadeh-Zavardehi, S., Tavakkoli-Moghaddam, R. & Lotfi, F.H. A modified imperialist competitive algorithm for scheduling single batch-processing machine with fuzzy due date. Int J Adv Manuf Technol 85, 2439–2458 (2016). https://doi.org/10.1007/s00170-015-8067-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-015-8067-1