Collaborative paradigm for single-machine scheduling under just-in-time principles: total holding-tardiness cost problem

• Autorzy: Varela M. L. R. , Madureira A. M. , Dantas J. D. , Santos A. S. , Putnik G. D. , Trojanowska J. , Machado J.

Identyfikatory

DOI

10.24425/119404

• Języki publikacji: EN

Abstrakty

EN

The problem of sequencing jobs on a single machine to minimize total cost (earliness and tardiness) is nowadays not just important due to traditional concerns but also due to its importance in the context of Collaborative Networked Organizations and Virtual Enterprises, where precision about promptly responses to customers’ requests, along with other important requirements, assume a crucial role. In order to provide a contribution in this direction, in this paper the authors contribute with an applied constructive heuristics that tries to find appropriate solutions for single machine scheduling problems under different processing times and due dates, and without preemption allowed. In this paper, two different approaches for single-machine scheduling problems, based on external and internal performance measures are applied to the problem and a comparative analysis is performed. Computational results are presented for the problem under Just-in-Time and agile conditions on which each job has a due date, and the objective is to minimize the sum of holding costs for jobs completed before their due date and tardiness costs for jobs completed after their due date. Additional computational tests were developed based on different customer and enterprise oriented performance criteria, although preference is given to customer-oriented measures, namely the total number of tardy jobs and the maximum tardiness.

Słowa kluczowe

EN

single-machine; scheduling; heuristics; just-in-time; agile manufacturing; holding-tardiness cost problem

• Wydawca: Production Engineering Committee of the Polish Academy of Sciences ; Polish Association for Production Management
• Czasopismo: Management and Production Engineering Review
• Rocznik: 2018
• Tom: Vol. 9, No. 1
• Strony: 90--103
• Opis fizyczny: Bibliogr. 61 poz., rys., tab., wykr.

Twórcy

autor

Varela M. L. R.

• University of Minho, School of Engineering, Department of Production and Systems, Azurem Campus, 4804–533, Guimaraes, Portugal

autor

Madureira A. M.

• Polytechnic Institute of Porto, School of Engineering, GECAD Research Group, Portugal

autor

Dantas J. D.

• University of Minho, School of Engineering, Department of Production and Systems, Portugal

autor

Santos A. S.

• University of Minho, School of Engineering, Department of Production and Systems, Portugal

autor

Putnik G. D.

• University of Minho, School of Engineering, Department of Production and Systems, Portugal

autor

Trojanowska J.

• Poznan University of Technology, Chair of Management and Production Engineering, Poland

autor

Machado J.

• University of Minho, School of Engineering, Department of Mechanical Engineering, Portugal

Bibliografia

• [1] Sika R., Rogalewicz M., Methodologies of knowledge discovery from data and Data Mining methods in mechanical engineering, Management and Production Engineering Review, ISSN (2080-8208), 7, 4, 97–108, 2016, doi: 10.1515/mper-2016-0040.
• [2] Pinto T., Varela L.R., Comparing extended neighborhood seardh techniques applied to production scheduling, The Romanian Review Precision Mechanics, Optics & Mechatronics, 20, 2010.
• [3] Madureira A., Ramos C., Silva S.C., Resourceoriented scheduling for real world manufacturing systems, IEEE International Symposium, pp. 140– 145, 2003.
• [4] Madureira A., Sousa N., Pereira I., Self-organization for scheduling in agile manufacturing, 10th IEEE International Conference on Cybernautic Intelligent Systems 2011, London, United Kingdom, 2011.
• [5] Madureira A., Pereira I., Pereira P., Abraham A., Negotiation mechanism for self-organized scheduling system with collective intelligence, Neurocomputing, 132, 97–110, 2014.
• [6] Klos S., Patalas-Maliszewska J., Using a simulation method for intelligent maintenance management, [in:] Intelligent Systems in Production Engineering and Maintenance, ISPEM 2017, Burduk A., Mazurkiewicz D. [Eds.], Cham, Springer International Publishing, Advances in Intelligent Systems and Computing, 637, 85–95, 2018.
• [7] Madureira A., Ramos C., do Carmo Silva S.D., A coordination mechanism for real world scheduling problems using genetic algorithms, Evaluation Computation, 1, 175–180, 2002.
• [8] Varela M.R.L, Trojanowska J., Carmo-Silva S., Costa N.M.L., Machado J., Comparative simulation study of production scheduling in the hybrid and the parallel flow, Management and Production Engineering Review, 8, 2, 69–80, 2017.
• [9] Madureira A., Santos J., Proposal of multi-agent based model for dynamic sheduling in manufacturing, WSEAS Transacions on Information Science & Applications, 2, 2005.
• [10] Madureira A., Pereira I., Intelligent Bio-Inspired system for manufacturing scheduling under uncertainties, Hybrid Intelligent Systems, pp. 109–112, 2010.
• [11] Koliński A., Śliwczyński B., Golińska-Dawson P., Evaluation model for production process economic efficiency, LogForum, 12(2), 129–145, 2016.
• [12] Kujawińska A., Rogalewicz M., Diering M., Application of expectation maximization method for purchase decision-making support in welding branch, Management and Production Engineering Review, 7, 2, 29–33, 2016.
• [13] Kawa A., Simulation of dynamic supply chain configuration based on software agents and graph theory, International Work-Conference on Artifi- cial Neural Networks, Springer Berlin Heidelberg, pp. 346–349, 2009.
• [14] Hamidreza H., Mohammad Ebrahim A., Keyvan Kamandani P., A branch and bound for single machine stochastic scheduling to minimize the maximum lateness, International Journal of Industrial Engineering Computations, 3b, 499, 2012.
• [15] Liu Z., Single machine scheduling to minimize maximum lateness subject to release dates and precedence constraints, Computers and Operations Research, 37, 1537–1543, 2010.
• [16] Jin F., Song S., Wu C.m, A simulated annealing algorithm for single machine scheduling problems with family setups, Computers and Operations Research, 36, 2133–2138, 2009.
• [17] Liu L., Zhou H., Applying variable neighborhood search to the single-machine maximum lateness rescheduling problem, Electronic Notes in Discrete Mathematics, 39, 107–114, 2012.
• [18] Cheng T.C.E., Wang G., Single machine scheduling with learning effect considerations, Annals of Operations Research, 98, 273–290, 2000.
• [19] Haddad H., Ghanbari P., Zeraatkar Moghaddam A., A new mathematical model for single machine batch scheduling problem for minimizing maximum lateness with deteriorating jobs, International Journal of Industrial Engineering Computations, 3, 253–264, 2012.
• [20] Subramanian A., Battarra M., Potts C.N., An iterated local search heuristic for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times, International Journal of Production Research, 52, 2729–2742, 2014.
• [21] Mohammad Mahdavi M., Hamidreza H., Mohammad M., Kazem A., A calibrated hybrid for the single machine scheduling problem with objective of minimizing total weighted tardiness with dependent setup, International Journal of Information, Business and Management, 4, p. 55, 2012.
• [22] Mosheiov G., Yovel U., Minimizing weighted earliness – tardiness and due-date cost with unit processing-time jobs, European Journal of Operational Research, 172, 528–544, 2006.
• [23] Lu C.-C., Lin S.-W., Ying K.-C., Robust scheduling on a single machine to minimize total flow time (Report), Computers & Operations Research, 39, 1682–1691, 2012.
• [24] Mor B., Mosheiov G., Single machine batch scheduling with two competing agents to minimize total flowtime, European Journal of Operational Research, 215, 524–531, 2011.
• [25] Jiyin L., MacCarthy B.L., Effective heuristics for the single machine sequencing problem with ready times, International Journal of Production Research, 29, 1521, 1991.
• [26] Low C.Y., Ji M., Hsu C.J., Su C.T., Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance, Appl. Math. Model., 34, 334–342, 2010.
• [27] Ji M., He Y., Cheng T.C.E., Single-machine scheduling with periodic maintenance to minimize makespan, Comput. Oper. Res., 34, 1764–1770, 2007.
• [28] He Y., Zhong W., Gu H., Improved algorithms for two single machine scheduling problems, Theoretical Computer Science, 363, 257–265, 2006.
• [29] Chaudhry I., Drake P., Minimizing flow-time variance in a single-machine system using genetic algorithms, Int. J. Adv. Manuf. Technol., 39, 355–366, 2008.
• [30] Al-Turki U., Fedjki C., Andijani A., Tabu search for a class of single- machine scheduling problems, Computers and Operations Research, 28, 1223–1230, 2001.
• [31] Pinedo M., Scheduling: theory, algorithms, and systems, Prentice Hall, 2002.
• [32] Brucker P., Scheduling algorithms, Springer, 2007.
• [33] Wan G., Yen B.P.C., Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs, European Journal of Operational Research, 195, 89–97, 2009.
• [34] Rahmani K., Mahdavi I., Moradi H., Khorshidian H., Solimanpur M., A nondominated ranked genetic algorithm for bi-objective single machine preemptive scheduling in just-in-time environment, International Journal of Advanced Manufacturing Technology, 55, 1135–1147, 2011.
• [35] Pathumnakul S., Egbelu P.J., Algorithm for minimizing weighted earliness penalty in single-machine problem, European Journal of Operational Research, 161, 780, 2005.
• [36] Wang X.-R., Huang X., Wang J.-B., Single-machine scheduling with linear decreasing deterioration to minimize earliness penalties, Applied Mathematical Modelling, 35, 3509–3515, 2011.
• [37] Chen W.Y., Sheen G.J., Single-machine scheduling with multiple performance measures: minimizing job-dependent earliness and tardiness subject to the number of tardy jobs, International Journal of Production Economics, 109, 214–229, 2007.
• [38] Hino C.M., Ronconi D.P., Mendes A.B., Minimizing earliness and tardiness penalties in a single-machine problem with a common due date, European Journal of Operational Research, 160, 190–201, 2005.
• [39] Bauman J., Józefowska J., Minimizing the earlinesstardiness costs on a single machine, Computers and Operations Research, 33, 3219–3230, 2006.
• [40] Mansour M.A.A.-F., A genetic algorithm for scheduling n jobs on a single machine with a stochastic controllable processing, tooling cost and earliness-tardiness penalties, (Report), American Journal of Engineering and Applied Sciences, 4, 341, 2011.
• [41] Wan L., Yuan J., Single-machine scheduling to minimize the total earliness and tardiness is strongly NP-hard, Operations Research Letters, 41, 363–365, 2013.
• [42] Shabtay D., Steiner G., The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times, Ann. Oper. Res., 159, 25–40, 2008.
• [43] Yoo W.S., Martin-Vega L.A., Scheduling singlemachine problems for on-time delivery, Comput. Ind. Eng., 39, 371–392, 2001.
• [44] Huo Y., Leung J.Y.T., Zhao H., Bi-criteria scheduling problems: number of tardy jobs and maximum weighted tardiness, European Journal of Operational Research, 177, 116–134, 2007.
• [45] Mohammad Mahavi M., Farzad Z., Farzad Firouzi J., A fuzzy modeling for single machine scheduling problem with deteriorating jobs, International Journal of Industrial Engineering Computations, 1, 147, 2010.
• [46] Mohammad K., Elnaz N., Amin A., Reza K., Justin-time preemptive single machine problem with costs of earliness/tardiness, interruption and workin-process, International Journal of Industrial Engineering Computations, 3, 321, 2012.
• [47] Abdul-Razaq T.S., Potts C.N., Dynamic programming state-space relaxation for single-machine scheduling, J. Opl. Res. Soc., 39(2), 141–152, 1988.
• [48] Sidney J.B., Optimal single-machine scheduling with earliness and tardiness penalties, J. Opl. Res. Soc., 25(1), 62–69, 1977.
• [49] Madureira A.M., Metaheuristics applications in sequencing problems [in Portuguese], Master Thesis, FEUP, 1995.
• [50] Rao R.V., Vivek P., An elitist teaching-learningbased optimization algorithm for solving complex constrained optimization problems, International Journal of Industrial Engineering Computations, 3, 535, 2012.
• [51] Trojanowska J., Żywicki K., Varela M.L.R., Machado J., Improving production flexibility in an industrial company by shortening changeover time: a triple helix collaborative project, [in:] Multiple Helix Ecosystems for Sustainable Competitiveness, PerisOrtiz M., Ferreira J., Farinha L., Fernandes N. [Eds.], Innovation, Technology and Knowledge Management, Springer, pp. 133–146, 2016.
• [52] Ivanov V., Mital D., Karpus V. et al., Numerical simulation of the system “fixture–workpiece” for lever machining, International Journal of Advanced Manufacturing Technology, 91, 79-90, 2017.
• [53] Varela M.L.R., do Carmo Silva S., An ontology for a model of manufacturing scheduling problems to be solved on the web, Innovation in Manufacturing Networks, [Ed.] Springer, pp. 197-204, 2008.
• [54] Babaei M., Mohammadi M., Ghomi S.M.T.F., Sobhanallahi M.A., Two parameter-tuned metaheuristic algorithms for the multi-level lot sizing and scheduling problem, International Journal of Industrial Engineering Computations, 3, 751, 2012.
• [55] Ouelhadj D., Petrovic S., A survey of dynamic scheduling in manufacturing systems, J. Sched., 12, 417–431, 2009.
• [56] Madureira A., Hybrid meta-heuristics based system for distributed dynamic scheduling, [in:] Encyclopedia of Artificial Intelligence, Rabuñal J.R., Dorado J., Prazos A. [Eds.], Idea Group Reference, Information Science Reference Ed., 2009.
• [57] Madureira A., Santos J., Pereira I., Hybrid intelligent system for distributed dynamic scheduling, Springer-Verlag, Ed., 2009.
• [58] Varela L.R., Ribeiro R.A., Evaluation of simulated annealing to solve fuzzy optimization problems, Journal of Intelligent and Fuzzy Systems, 14, 59–71, 2003.
• [59] Varela M.L.R., Putnik G.D., Cruz-Cunha M.M., Web-based technologies integration for distributed manufacturing scheduling in a virtual enterprise, International Journal of Web Portals (IJWP), 4, 19–34, 2012.
• [60] Ribeiro R.A., Varela L.R., Fuzzy optimization using simulated annealing: an example set, Fuzzy Sets Based Heuristics for Optimization, Ed.: Springer, pp. 159–180, 2003.
• [61] Dantas J.D., Varela L.R., Scheduling single-machine problem based on just-in-time principles, Proceedings of the Sixth World Congress on Nature and Biologically Inspired Computing (NaBIC’14), pp. 164–169, 2014.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).