Towards a Standardization in Scheduling Models: Assessing the Variety of Homonyms

Authors: Marcel Rojahn, Edzard Weber, Norbert Gronau

Abstract:

Terminology is a critical instrument for each researcher. Different terminologies for the same research object may arise in different research communities. By this inconsistency, many synergistic effects get lost. Theories and models will be more understandable and reusable if a common terminology is applied. This paper examines the terminological (in)consistence for the research field of job-shop scheduling by a literature review. There is an enormous variety in the choice of terms and mathematical notation for the same concept. The comparability, reusability and combinability of scheduling methods is unnecessarily hampered by the arbitrary use of homonyms and synonyms. The acceptance in the community of used variables and notation forms is shown by means of a compliance quotient. This is proven by the evaluation of 240 scientific publications on planning methods.

Keywords: Job-shop scheduling, JSP, terminology, notation, standardization.

References:

[1] Siegel, T. (1974). Optimale Maschinenbelegungsplanung: Zweckmaessigkeit der Zielkriterien und Verfahren zur Loesung des Reihenfolgeproblems. Schmidt, Berlin.
[2] DIN Deutsches Institut für Normung e.V. (2001). Grundlagen der Normungsarbeit des DIN, DIN-Normenheft. Beuth, Berlin.
[3] Staples, M., & Niazi, M. (2007). Experiences using systematic review guidelines. J. Syst. Softw. 80.
[4] Bless, C., Higson-Smith, C., & Kagee, A. (2006). 4th. ed. Fundamentals of social research methods. An African perspective. Juta, Cape Town.
[5] Kitchenham, B. (2004). Procedures for Performing Systematic Reviews (No. TR/SE0401 resp. 0400011T.1). Keele University resp. National ICT Australia.
[6] Kitchenham, B., & Charters, S. (2007). Guidelines for performing Systematic Literature reviews in Software Engineering Version 2.3 (No. EBSE-2007-01). Keele University and University of Durham.
[7] Petticrew, M., & Roberts, H. (2005). Systematic reviews in the social sciences: a practical guide. Blackwell Pub., Malden, MA.
[8] Anilkumar, G., & Tanprasert, T. (2006). Neural Network Based Generalized Job-Shop Scheduler, in: Proceedings of the 2nd IMT-GT Regional Conference on Mathematics, Statistics and Applications. University sains Malaysia, Penang.
[9] Albers, S., & Schmidt, G. (2001). Scheduling with unexpected machine breakdowns. Discrete Applied Mathematics. Discrete Appl. Math, 110, 85–99.
[10] Bertsimas, D., Gamarnik, D., & Sethuraman, J. (2003). From Fluid Relaxations to Practical Algorithms for High-Multiplicity Job-Shop Scheduling: The Holding Cost Objective. Oper. Res. 51, 798–813.
[11] Chen, Bo, et al. "On-line scheduling of small open shops." Discrete Applied Mathematics 110.2-3 (2001): 133-150.
[12] Knust, Sigrid, et al. "Shop scheduling problems with pliable jobs." Journal of Scheduling 22 (2019): 635-661.
[13] Yunes, Tallys, Ionuţ D. Aron, and John N. Hooker. "An integrated solver for optimization problems." Operations Research 58.2 (2010): 342-356.
[14] K. Belkadi, M. Gougand, M. Benyettou, A. Aribi: „Sequential and Parallel Genetic Algorithms for the Hybrid Shop Scheduling Problem” Journal of Applied Science 6, (2006): 775­-778
[15] Johannes, Berit. "Scheduling parallel jobs to minimize the makespan." Journal of Scheduling 9 (2006): 433-452.
[16] Ahmadi-Javid, Amir, and Pedram Hooshangi-Tabrizi. "A mathematical formulation and anarchic society optimisation algorithms for integrated scheduling of processing and transportation operations in a flow-shop environment." International journal of production research 53.19 (2015): 5988-6006.
[17] Ying, Kuo-Ching, Shih-Wei Lin, and Shu-Yen Wan. "Bi-objective reentrant hybrid flowshop scheduling: an iterated Pareto greedy algorithm." International Journal of Production Research 52.19 (2014): 5735-5747.
[18] Meeran, Sheik, and M. S. Morshed. "Evaluation of a hybrid genetic tabu search framework on job shop scheduling benchmark problems." International Journal of Production Research 52.19 (2014): 5780-5798.
[19] Framinan, Jose M., Paz Perez-Gonzalez, and Victor Fernandez-Viagas. "Deterministic assembly scheduling problems: A review and classification of concurrent-type scheduling models and solution procedures." European Journal of Operational Research 273.2 (2019): 401-417.
[20] Mönch, Lars, et al. "A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations." Journal of scheduling 14 (2011): 583-599.
[21] He, Wei, and Di-hua Sun. "Scheduling flexible job shop problem subject to machine breakdown with route changing and right-shift strategies." The International Journal of Advanced Manufacturing Technology 66 (2013): 501-514.
[22] Gafarov, Evgeny R., Alexandre Dolgui, and Frank Werner. "A new graphical approach for solving single-machine scheduling problems approximately." International Journal of Production Research 52.13 (2014): 3762-3777.
[23] Naderi-Beni, Mahdi, et al. "Fuzzy bi-objective formulation for a parallel machine scheduling problem with machine eligibility restrictions and sequence-dependent setup times." International Journal of Production Research 52.19 (2014): 5799-5822.
[24] Masin, Michael, and Tal Raviv. "Linear programming-based algorithms for the minimum makespan high multiplicity jobshop problem." Journal of Scheduling 17 (2014): 321-338.
[25] Pan, Ershun, et al. "Single-machine group scheduling problem considering learning, forgetting effects and preventive maintenance." International Journal of Production Research 52.19 (2014): 5690-5704.
[26] Li, Qingwei, and R. John Milne. "A production scheduling problem with sequence-dependent changeover costs." International Journal of Production Research 52.13 (2014): 4093-4102.
[27] Ou, Jinwen, Xiangtong Qi, and Chung-Yee Lee. "Parallel machine scheduling with multiple unloading servers." Journal of Scheduling 13 (2010): 213-226.
[28] Liu, Aijun, John Fowler, and Michele Pfund. "Dynamic co-ordinated scheduling in the supply chain considering flexible routes." International Journal of Production Research 54.1 (2016): 322-335.
[29] Xu, Xiaoqing, Jun Lin, and Wentian Cui. "Hedge against total flow time uncertainty of the uniform parallel machine scheduling problem with interval data." International Journal of Production Research 52.19 (2014): 5611-5625.
[30] Tsai, Cheng-Fa, and Feng-Cheng Lin. "A new hybrid heuristic technique for solving job-shop scheduling problem." Second IEEE International Workshop on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications, 2003. Proceedings. IEEE, 2003.
[31] Feng, Jianguang, Ada Che, and Nengmin Wang. "Bi-objective cyclic scheduling in a robotic cell with processing time windows and non-Euclidean travel times." International Journal of Production Research 52.9 (2014): 2505-2518.
[32] Wong, C. S., Felix TS Chan, and Sai Ho Chung. "Decision-making on multi-mould maintenance in production scheduling." International Journal of Production Research 52.19 (2014): 5640-5655.
[33] Liu, Li-Lan, et al. "A hybrid PSO-GA algorithm for job shop scheduling in machine tool production." International Journal of Production Research 53.19 (2015): 5755-5781.
[34] Anilkumar, K. G., and T. Tanprasert. "A Subjective Scheduler Based on Backpropagation Neural Network for Formulating a Real-life Scheduling Situation." International Journal of Computer and Information Engineering 2.9 (2008): 3151-3157.
[35] Zheng, Yan, Yujie Xiao, and Yoonho Seo. "A tabu search algorithm for simultaneous machine/AGV scheduling problem." International Journal of Production Research 52.19 (2014): 5748-5763.
[36] Liu, Lu, Jian-Jun Wang, and Xiao-Yuan Wang. "Single machine due-window assignment scheduling with resource-dependent processing times to minimise total resource consumption cost." International Journal of Production Research 54.4 (2016): 1186-1195.
[37] Tan, Mao, Bin Duan, and Yongxin Su. "Economic batch sizing and scheduling on parallel machines under time-of-use electricity pricing." Operational Research 18 (2018): 105-122.
[38] Mattfeld, Dirk C., and Christian Bierwirth. "An efficient genetic algorithm for job shop scheduling with tardiness objectives." European journal of operational research 155.3 (2004): 616-630.
[39] Fekih, Asma, Olfa Jellouli, and Atidel Boubaker Hadj-Alouane. "Flexible job-shop scheduling problem by genetic algorithm and learning by partial injection of sequences." International Journal of Engineering Management and Economics 2 3.1-2 (2012): 22-39.
[40] Albers, Susanne, and Guenter Schmidt. "Scheduling with unexpected machine breakdowns." Discrete Applied Mathematics 110.2-3 (2001): 85-99.
[41] Xu, Dehua, Yunqiang Yin, and Hongxing Li. "Scheduling jobs under increasing linear machine maintenance time." Journal of scheduling 13 (2010): 443-449.
[42] Gonçalves, José Fernando, Jorge José de Magalhães Mendes, and Maurı́cio GC Resende. "A hybrid genetic algorithm for the job shop scheduling problem." European journal of operational research 167.1 (2005): 77-95.
[43] Sun, Di-hua, et al. "Scheduling flexible job shop problem subject to machine breakdown with game theory." International Journal of Production Research 52.13 (2014): 3858-3876.
[44] Anilkumar, Kothalil Gopalakrishnan, and Thitipong Tanprasert. "Generalized job-shop scheduler using feed forward neural network and greedy alignment procedure." Artificial Intelligence and Applications. 2007.
[45] Garrido, Antonio, et al. "Heuristic methods for solving job-shop scheduling problems." Proc. ECAI-2000 Workshop on New Results in Planning, Scheduling and Design (PuK2000). 2000.
[46] De Farias, Daniela Pucci, and Benjamin Van Roy. "The linear programming approach to approximate dynamic programming." Operations research 51.6 (2003): 850-865.
[47] Fettke, P., Houy, C., & Loos, P. (2010a). Zur Bedeutung von Gestaltungswissen fuer die gestaltungsorientierte Wirtschaftsinformatik. Konzeptionelle Grundlagen, Anwendungsbeispiel und Implikationen. Wirtschaftsinformatik 52, 339–352.
[48] Fettke, P., Houy, C., & Loos, P. (2010b). Zur Bedeutung von Gestaltungswissen fuer die gestaltungsorientierte Wirtschaftsinformatik - Ergaenzende Ueberlegungen und weitere Anwendungsbeispiele (Arbeitsbericht No. 191). Institut für Wirtschaftsinformatik im Deutschen Forschungszentrum fuer Kuenstliche Intelligenz (DFKI), Saarbruecken.
[49] Frank, U. (2010). Zur methodischen Fundierung der Forschung in der Wirtschaftsinformatik. In: Oesterle, H., Winter, R., & Brenner, W. (Eds.), Gestaltungsorientierte Wirtschaftsinformatik: Ein Plaedoyer Fuer Rigor Und Relevanz (pp. 35–44). Eigenverlag.
[50] Houy, C., Fettke, P., & Loos, P. (2009). Stilisierte Fakten der Ereignisgesteuerten Prozesskette - Anwendung einer Methode zur Theoriebildung in der Wirtschaftsinformatik. In: Nuettgens, M., Rump, F.J., Mendling, J., & Gehrke, N. (Eds.), EPK 2009. GI-Workshop: Geschäftsprozessmanagement Mit Ereignisgesteuerten Prozessketten (WI-EPK-09), November 26-27, Berlin, Germany. Gesellschaft für Informatik, Bonn, pp. 22–41.
[51] Houy, C., Fettke, P., & Loos, P. (2011). Stilisierte Fakten in der gestaltungsorientierten Wirtschaftsinformatik - Allgemeine Potentiale und erste Erfahrungen. In: Bernstein, A., & Schwabe, G. (Eds.), Wirtschaftinformatik Proceedings 2011.
[52] Tichy, G. (1994). Konjunktur - Stilisierte Fakten, Theorie, Prognose, 2nd ed. Springer, Heidelberg.
[53] Zelewski, S. (2007). Kann Wissenschaftstheorie behilflich für die Publikationspraxis sein? - Eine kritische Auseinandersetzung mit den ,,Guideline” von Hevner et al., in: Lehner, F., & Zelewski, S. (Eds.), Wissenschaftstheoretische Fundierung und wissenschaftliche Orientierung der Wirtschaftsinformatik (pp. 71–120), GITO, Berlin.
[54] Brüggemann, D. (2010). Ein parametrisierbares Verfahren zur Aenderungsplanung fuer den Flexible Flow Shop mit integrierter Schichtmodellauswahl. PhD Thesis, University of Paderborn.