Job-shop like manufacturing system with variable power threshold and operations with power requirementsFootnote

This article is an extended and improved version of two conference papers (Kemmoé, Lamy, and Tchernev Citation2015a, Kemmoé, Lamy, and Tchernev Citation2015b). The mathematical model is improved. The Local search procedure is improved and formalised. A construction heuristic is also introduced to generate good starting solutions. The data-set is extended with medium scale instances. Experiments are given.

References

• Adibi, M. A., M. Zandieh, and M. Amiri. 2010. “Multi-objective Scheduling of Dynamic Job Shop Using Variable Neighborhood Search.” Expert Systems with Applications 37: 282–287.10.1016/j.eswa.2009.05.001
   Web of Science ®Google Scholar
• Bierwirth, C. 1995. “A Generalized Permutation Approach to Job Shop Scheduling with Genetic Algorithms.” OR Spektrum 17: 87–92.10.1007/BF01719250
   Google Scholar
• Binato, S., W. J. Hery, D. M. Loewenstern, and M. G. C. Resende. 2001. “A Greedy Randomized Adaptive Search Procedure for Job Shop Scheduling.” IEEE Transactions on Power Systems 16: 247–253.10.1109/59.918294
   Web of Science ®Google Scholar
• Bruzzone, A. A. G., D. Anghinolfi, M. Paolucci, and F. Tonelli. 2012. “Energy-aware Scheduling for Improving Manufacturing Process Sustainability: A Mathematical Model for Flexible Flow Shops.” CIRP Annals – Manufacturing Technology 61: 459–462.
   Web of Science ®Google Scholar
• Caumond, A., P. Lacomme, and N. Tchernev. 2008. “A Memetic Algorithm for the Job-shop with Time-Lags.” Computers and Operations Research 35: 2331–2356.10.1016/j.cor.2006.11.007
   Web of Science ®Google Scholar
• Cheng, R., M. Gen, and Y. Tsujimura. 1996. “A Tutorial Survey of Job-shop Scheduling Problems Using Genetic Algorithms – I Representation.” Computers & Industrial Engineering 30: 983–997.10.1016/0360-8352(96)00047-2
   Web of Science ®Google Scholar
• Cheng, T. C. E., B. Peng, and Z. Lu. 2016. “A Hybrid Evolutionary Algorithm to Solve the Job Shop Scheduling Problem.” Annals of Operations Research 242: 223–237.
   Google Scholar
• Dai, M., D. Tang, A. Giret, M. A. Salido, and W. D. Li. 2013. “Energy-efficient Scheduling for a Flexible Flow Shop Using an Improved Genetic-simulated Annealing Algorithm.” Robotics and Computer-Integrated Manufacturing 29: 418–429.10.1016/j.rcim.2013.04.001
   Web of Science ®Google Scholar
• Duflou, J. R., J. W. Sutherland, D. Dornfeld, C. Hermann, J. Jeswiet, S. Kara, M. Hauschild, and K. Kellens. 2012. “Towards Energy and Resource Efficient Manufacturing: A Processes and Systems Approach.” CIRP Annals – Manufacturing Technology 61: 587–609.
   Web of Science ®Google Scholar
• Duhamel, C., P. Lacomme, and C. Prodhon. 2011. “Efficient Frameworks for Greedy Split and New Depth First Search Split Procedures for Routing Problems.” Computers & Operations Research 38 (4): 723–739.10.1016/j.cor.2010.09.010
   Web of Science ®Google Scholar
• (EIA) Energy Administration Information. 2013. International Energy Outlook. http://www.eia.gov/
   Google Scholar
• Fang, K., N. Uhan, F. Zhao, and J. W. Sutherland. 2011. “A New Approach to Scheduling in Manufacturing for Power Consumption and Carbon Footprint Reduction.” Journal of Manufacturing Systems 30: 234–240.10.1016/j.jmsy.2011.08.004
   Web of Science ®Google Scholar
• Feo, T. A., M. G. C. Resende, and S. H. Smith. 1994. “A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set.” Operations Research 42: 860–878.10.1287/opre.42.5.860
   Web of Science ®Google Scholar
• Gao, L., X. Li, X. Wen, C. Lu, and F. Wen. 2015. “A Hybrid Algorithm Based on a New Neighborhood Structure Evaluation Method for Job Shop Scheduling Problem.” Computers and Industrial Engineering 88: 417–429.10.1016/j.cie.2015.08.002
   Web of Science ®Google Scholar
• Garey, M. R., D. S. Johnson, and R. Sethi. 1976. “The Complexity of flow Shop and Job-shop Scheduling.” Mathematics of Operations Research 1 (2): 117–129.10.1287/moor.1.2.117
   Google Scholar
• Giret, A., D. Trentesaux, and V. Prabhu. 2015. “Sustainability in Manufacturing Operations Scheduling: A State of the Art Review.” Journal of Manufacturing Systems 37: 126–140.10.1016/j.jmsy.2015.08.002
   Web of Science ®Google Scholar
• Gupta, A., and S. Venkataraman. 2013. “Reducing Price Volatility of Electricity Consumption for a Firm’s Energy Risk Management.” The Electricity Journal 26 (3): 89–105.10.1016/j.tej.2013.03.005
   Google Scholar
• He, Y., Y. Li, T. Wu, and J. W. Sutherland. 2015. “An Energy-responsive Optimization Method for Machine Tool Selection and Operation Sequence in Flexible Machining Job Shops.” Journal of Cleaner Production 87: 245–254.10.1016/j.jclepro.2014.10.006
   Web of Science ®Google Scholar
• Kemmoé-Tchomté, S., D. Lamy, and N. Tchernev. 2015a. “An Optimization Framework for Job-shop with Energy Threshold Issue with Consideration of Machining Operations with Consumption Peaks.” Proceedings of the 2015 Multidisciplinary International Scheduling Conference (MISTA), Prague, Czech Republic, 118–133.
   Google Scholar
• Kemmoé-Tchomté, S., D. Lamy, and N. Tchernev. 2015b. “Job-shop like Manufacturing System with Time Dependent Energy Threshold and Operations with Peak Consumptions.” In APMS 2015, Part I, IFIP AICT, edited by S. Umeda, M. Nakano, H. Mizuyama, N. Hibino, D. Kiritsis, and G. von Cieminski, vol. 459, 617–624. Tokyo, Japan.
   Google Scholar
• Kurdi, M. 2015. “A New Hybrid Island Model Genetic Algorithm for Job Shop Scheduling Problem.” Computers and Industrial Engineering 88: 273–283.10.1016/j.cie.2015.07.015
   Web of Science ®Google Scholar
• Lawrence, S. 1984. Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques (Supplement). Pittsburgh, PA: Graduate School of Industrial Administration, Carnegie Mellon University.
   Google Scholar
• Lei, D., Y. Zheng, and X. Guo. 2016. “A Shuffled Frog-leaping Algorithm for Flexible Job Shop Scheduling with the Consideration of Energy Consumption.” International Journal of Production Research 55 (11): 3126–3140. doi:10.1080/00207543.2016.1262082.
   PubMed Web of Science ®Google Scholar
• Liu, C. H. 2015. “Mathematical Programming Formulations for Single-machine Scheduling Problems While Considering Renewable Energy Uncertainty.” International Journal of Production Research 54: 1122–1133 doi:10.1080/00207543.2015.1048380.
   Web of Science ®Google Scholar
• Liu, Y., H. Dong, N. Lohse, S. Petrovic, and N. Gindy. 2014. “An Investigation into Minimising Total Energy Consumption and Total Weighted Tardiness in Job Shops.” Journal of Cleaner Production 65: 87–96.10.1016/j.jclepro.2013.07.060
   Web of Science ®Google Scholar
• Liu, Y., H. Dong, N. Lohse, and S. Petrovic. 2015. “Reducing Environmental Impact of Production during a Rolling Blackout Policy – A Multi Objective Schedule Optimisation Approach.” Journal of Cleaner Production 102: 418–427.10.1016/j.jclepro.2015.04.038
   Web of Science ®Google Scholar
• Liu, G. S., H. D. Yang, and M. B. Cheng. 2016. “A Three-stage Decomposition Approach for Energy-aware Scheduling with Processing-time-dependent Product Quality.” International Journal of Production Research 55: 3073–3091. doi:10.1080/00207543.2016.1241446.
   Web of Science ®Google Scholar
• Luo, H., B. Du, G. Q. Huang, H. Chen, and X. Li. 2013. “Hybrid Flow Shop Scheduling Considering Machine Electricity Consumption Cost.” International Journal of Production Economics 146: 423–439.10.1016/j.ijpe.2013.01.028
   Web of Science ®Google Scholar
• May, G., B. Stahl, M. Taisch, and V. Prabhu. 2015. “Multi-objective Genetic Algorithm for Energy Efficient Job-shop Scheduling.” International Journal of Production Research 53 (23): 7071–7089.10.1080/00207543.2015.1005248
   Web of Science ®Google Scholar
• Merkert, L., I. Harjunkoski, A. Isaksson, S. Säynevirta, A. Saarela, and G. Sand. 2015. “Scheduling and Energy – Industrial Challenges and Opportunities.” Computers and Chemical Engineering 72: 183–198.10.1016/j.compchemeng.2014.05.024
   Web of Science ®Google Scholar
• Moon, J. Y., and J. Park. 2014. Smart Production Scheduling with Time-dependent and Machine-dependent Electricity Cost by Considering Distributed Energy Resources and Energy Storage, International Journal of Production Research 52 (13): 3922–3939. doi:10.1080/00207543.2013.860251.
   Google Scholar
• Mouzon, G. C., M. B. Yildirim, and J. Twomey. 2007. “Operational Methods for Minimization of Energy Consumption of Manufacturing Equipment.” International Journal of Production Research 45: 4247–4271.10.1080/00207540701450013
   Web of Science ®Google Scholar
• Nguyen, V. P., C. Prins, and C. Prodhon. 2012. “A Multi-start Iterated Local Search with Tabu List and Path Relinking for the Two-echelon Location-routing Problem.” Engineering Applications of Artificial Intelligence 25: 56–71.10.1016/j.engappai.2011.09.012
   Web of Science ®Google Scholar
• Nolde, K., and M. Morari. 2010. “Electrical Load Tracking Scheduling of a Steel Plant.” Computers and Chemical Engineering 34: 1899–1903.10.1016/j.compchemeng.2010.01.011
   Web of Science ®Google Scholar
• Nowicki, E., and C. Smutnicki. 1996. “A Fast Taboo Search for the Job Shop Problem.” Management Science 42 (6): 797–813.
   Web of Science ®Google Scholar
• O’Rielly, K., and J. Jeswiet. 2014. “Strategies to Improve Industrial Energy Efficiency.” 21st CIRP Conference on Life Cycle Engineering, Procedia CIRP, vol. 15, 325–330. Trondheim, Norway.
   Google Scholar
• Prins, C. 2009. “A GRASP X Evolutionary Local Search Hybrid for the Vehicle Routing Problem.” In Bio-inspired Algorithms for the Vehicle Routing Problem, Studies in Computational Intelligence, edited by F. B. Pereira and J. Tavares, vol. 161, 35–53. Springer Berlin Heidelberg.
   Google Scholar
• Qing-dao-er-ji, R., and Y. Wang. 2012. “A New Hybrid Genetic Algorithm for Job Shop Scheduling Problem.” Computers & Operations Research 39: 2291–2299.10.1016/j.cor.2011.12.005
   Web of Science ®Google Scholar
• Rager, M., C. Gahm, and F. Denz. 2015. “Energy-oriented Scheduling Based on Evolutionary Algorithms.” Computers & Operations Research 54: 218–231.10.1016/j.cor.2014.05.002
   Web of Science ®Google Scholar
• Roshanaei, V., B. Naderi, F. Jolai, and M. Khalili. 2009. “A Variable Neighborhood Search for Job Shop Scheduling with Set-up times to Minimize Makespan.” Future Generation Computer Systems 25: 654–661.10.1016/j.future.2009.01.004
   Web of Science ®Google Scholar
• Roy, B., and B. Sussman. 1964. “Les Problèmes D’ordonnancement Avec Contraintes Disjonctives.” Note DS No. 9 bis, SEMA Paris.
   Google Scholar
• Salido, M. A., J. Escamilla, F. Barber, A. Giret, D. Tang, and M. Dai. 2016. “Energy Efficiency, Robustness, and Makespan Optimality in Job-shop Scheduling Problems.” Artificial Intelligence for Engineering Design Analysis and Manufacturing 30 (3): 300–312.
   Web of Science ®Google Scholar
• Salido, Miguel A., Joan Escamilla, Adriana Giret, and Federico Barber. 2016. “A Genetic Algorithm for Energy-Efficiency in Job-Shop Scheduling.” The International Journal of Advanced Manufacturing Technology 85 (5–8): 1303–1314.
   Web of Science ®Google Scholar
• Shrouf, F., J. Ordieres-Meré, A. García-Sánchez, and M. Ortega-Mier. 2014. “Optimizing the Production Scheduling of a Single Machine to Minimize Total Energy Consumption Costs.” Journal of Cleaner Production 67: 197–207.10.1016/j.jclepro.2013.12.024
   Web of Science ®Google Scholar
• Van Laarhoven, P. J. M., E. H. L. Aarts, and J. K. Lenstra. 1992. “Job Shop Scheduling by Simulated Annealing.” Operations Research 40 (1): 113–125.10.1287/opre.40.1.113
   Web of Science ®Google Scholar
• Weinert, N., S. Chiotellis, and G. Seliger. 2011. “Methodology for Planning and Operating Energy-efficient Production Systems.” CIRP Annals – Manufacturing Technology 60: 41–44.10.1016/j.cirp.2011.03.015
   Web of Science ®Google Scholar
• Wolf, S., and P. Merz. 2007. “Evolutionary Local Search for the Super-peer Selection Problem and the P-Hub Median Problem.” Lecture Notes in Computer Science, Berlin, Springer 4771: 1–15.10.1007/978-3-540-75514-2
   Google Scholar
• Zhang, C. Y., P. Li, Y. Rao, and Z. Guan. 2008. “A Very Fast TS/SA Algorithm for the Job Shop Scheduling Problem.” Computers & Operations Research 35: 282–294.10.1016/j.cor.2006.02.024
   Web of Science ®Google Scholar
• Zhang, H., F. Zhao, K. Fang, and J. W. Sutherland. 2014. “Energy-conscious Flow Shop Scheduling under Time-of-use Electricity Tariffs.” CIRP Annals – Manufacturing Technology 63: 37–40.10.1016/j.cirp.2014.03.011
   Web of Science ®Google Scholar
• Zhang, L., X. Li, L. Gao, and G. Zhang. 2016. “Dynamic Rescheduling in FMS That is Simultaneously Considering Energy Consumption and Schedule Efficiency.” The International Journal of Advanced Manufacturing Technology 87 (5): 1387–1399. 10.1007/s00170-012-4294-x
   Web of Science ®Google Scholar
• Zhang, R., and R. Chiong. 2016. “Solving the Energy-Efficient Job Shop Scheduling Problem: A Multi-Objective Genetic Algorithm with Enhanced Local Search for Minimizing the Total Weighted Tardiness and Total Energy Consumption.” Journal of Cleaner Production 112 (4): 3361–3375.
   Web of Science ®Google Scholar
• Zhao, F., J. Zhang, C. Zhang, and J. Wang. 2015. “An Improved Shuffled Complex Evolution Algorithm with Sequence Mapping Mechanism for Job Shop Scheduling Problems.” Expert Systems with Applications 42: 3953–3966.10.1016/j.eswa.2015.01.007
   Web of Science ®Google Scholar