Abstract
Interval number theory has been applied to many fields; however, its applications to production scheduling are seldom investigated. In this paper, interval theory is used for its low cost in uncertainty modeling and novel interval job shop scheduling problem is proposed. To build the schedule of the problem, the addition and comparison of two interval numbers are first introduced and then a decoding procedure is constructed by using the chromosome of operation-based representation. It is proved that the possible actual objective values are contained in interval objective. An effective genetic algorithm (GA) is presented and tested by using some randomly generated instances. Computational results show the effectiveness of the GA.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Sakawa M, Mori T (1999) An efficient genetic algorithm for job shop scheduling problems with fuzzy processing time and fuzzy due date. Comput Ind Eng 36:325–341
Sakawa M, Kubota R (2000) Fuzzy programming for multi-objective job shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithm. Eur J Oper Res 120:393–407
Li FM, Zhu YL, Yin CW, Song XY (2005) Fuzzy programming for multi-objective fuzzy job shop scheduling with alternative machines through genetic algorithm. In: Wang L, Chen K, Ong YS (eds) Advance in Natural Computation. Springer, New York, pp 992–1004
Song XY., Zhu YL., Yin CW., Li FM. (2006) Study on the combination of genetic algorithms and ant colony algorithms for solving fuzzy job shop scheduling problems. In Proceedings of IMACS multi-conferences on computational engineering in systems applications, 1904–1909
Niu Q, Jiao B, Gu XS (2008) Particle swarm optimization combined with genetic operators for job shop scheduling problem with fuzzy processing time. Appl Math Comput 205:148–158
Lei DM (2008) Pareto archive particle swarm optimization for multi-objective fuzzy job shop scheduling problems. Int J Adv Manuf Technol 37:157–165
Petrovic S, Fayad C, Petrovic D, Burke E, Kendall G (2008) Fuzzy job shop scheduling with lot-sizing. Annals of Operational Research 159:275–292
Lei DM (2010) A genetic algorithm for flexible job shop scheduling with fuzzy processing time. Int J Prod Res 48:2995–3013
Lei DM (2010) Solving fuzzy job shop scheduling using random key genetic algorithm. Int J Adv Manuf Technol 49:253–262
Tavakkoli-Moghaddam R, Jolai F, Vaziri F, Ahmed PK, Azaron A (2005) A hybrid method for solving stochastic job shop scheduling problem. Appl Math Comput 170:185–206
Hu YM, Yin MH, Li XT (2011) A novel objective function for job-shop scheduling problem with fuzzy processing time and fuzzy due date using differential evolution algorithm. Int J Adv Manuf Technol, in press
Lei DM (2011) Scheduling stochastic job shop scheduling subject to random breakdown to minimize makespan. Int J Adv Manuf Technol 55:1183–1192
Gu JW, Gu XS, Gu M (2009) A novel parallel quantum genetic algorithm for stochastic job shop scheduling. J Math Anal Appl 355:63–81
Gu JW, Gu M, Gu XS (2010) A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem. Comput Oper Res 37:927–937
Moore RE (1979) Methods and applications of interval analysis. Prentice-Hall, London
Hao PY (2009) Interval regression analysis using support vector networks. Fuzzy Sets and Systems 160:2466–2485
Lhommeau M, Hardouin L, Cottenceau B, Jaulin L (2004) Interval analysis and dioid: application to robust controller design for timed event graphs. Automatica 40:1923–1930
Jiang C, Han X, Liu GR, Liu GP (2008) A nonlinear interval number programming method for uncertain optimization problems. Eur J Oper Res 188:1–13
Sengupta A, Pal TK (2000) On comparing interval numbers. Eur J Oper Res 127:28–43
Ishibuchi H, Tanaka M (1990) Multiobjective programming in optimization of the interval objective function. Eur J Oper Res 48:219–225
Cheng RW, Gen M, Tsujimura Y (1996) A tutorial survey of job-shop scheduling problems using genetic algorithms: I. Representation. Comput Ind Eng 30:983–997
Goldberg DE, Deb K (1991) A comparative analysis of selection schemes used in genetic algorithms. In: Rawlins G (ed) Foundations of genetic algorithms. Morgan Kaufmann, New York
Bierwirth C (1995) A generalized permutation approach for job shop scheduling with genetic algorithms. OR Spectrum, Special issue: Applied Local Search 17(1):87–92
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lei, D. Interval job shop scheduling problems. Int J Adv Manuf Technol 60, 291–301 (2012). https://doi.org/10.1007/s00170-011-3600-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-011-3600-3