The Problem of Scheduling a Single Machine by Considering Variable Priorities and Release Times

Document Type : Research Paper

Authors

1 Assistant Professor, Department of Industrial Engineering, Faculty of Industrial Engineering, Khajeh Nasir al-Din Tusi University of Technology, Tehran, Iran

2 PhD Student in Industrial Engineering, Department of Industrial Engineering, Faculty of Industrial Engineering, Khajeh Nasir al-Din Tusi University of Technology, Tehran, Iran

Abstract

In recent years, with the competitive environment, the importance of on time delivery and customer satisfaction is crucial. The objective functions, such as minimizing the number of tardy jobs, have attracted an increasing attention. This study aims to schedule the operations by minimizing the number of weighted tardy jobs in two modes of delay with a financial penalty and delay with lost sales. In this paper, the start time of operation is a decision variable. Furthermore, the operations can be only pursued one time, but the time of their availability is considered uncertain. In addition, the completion time of each operation is variable in two intervals; At the beginning of the interval, the delivery time of the task is considered without any penalty while at the end of the interval, the delivery time is determined with a penalty. As another innovation, this research examines the priority of variables so that by approaching the due dates and deadlines as well as the degree of customer urgency. It is updated based on some factors including the weight of the product order and the remaining processing time. In this paper, first the mathematical problem formulation is established and then a heuristic algorithm is used to solve the proposed model and find near-optimal solutions. To accomplish that, 2700 sample problems are generated and each is solved by GAMS software and the mentioned heuristic algorithm. The obtained results show the satisfactory performance of the heuristic algorithm in obtaining the near-optimal solution in a reasonable time.

Keywords

References

  • Baker, K.R., Introduction to sequencing and scheduling, John Wily, New York, 1974.
  • Chen, J.S., “Optimization models for the machine scheduling problem with a single flexible maintenance activity”, Engineering Optimization, Vol., No., 2006.
  • Mashkani, O., Moslehi, Gh., (2018) Minimizing the Number of Tardy Jobs in the Single Machine Scheduling Problem under Bimodal Flexible and Periodic Availability Constraints, International Journal of Industrial Engineering & Production Research, 29(1), pp. 15-34.
  • جواد بهنامیان و فاطمه کمیجانی (1397)، ارائه الگوریتم شاخه و برش برای حل مسأله زمان‌بندی تولید کارگاهی با استفاده از نامعادلات معتبر، نشـریه پـژوهـش‌های مهنـدسـی صنــایع در سیستـم‌هـای تولیــد، پاییز و زمستان 1397، سال ششم، شماره سیزدهم، صفحـــه 931-991.
  • Terekhov, D., Tran, T., Down, D., BECK, Ch., (2014) Integrating Queueing Theory and Schedulingfor Dynamic Scheduling Problems, Journal of Arti_cial Intelligence Research, 50(7), pp. 535-572.
  • مجید حسین­زاده و راشد صحرائیان (1396)، حل مسأله زمان‌بندی چندعاملی در محیط جریان کارگاهی با درنظر گرفتن اثر زمانی و رد کردن کارها با استفاده از یک الگوریتم فراابتکاری، نشـریه پـژوهـش‌های مهنـدسـی صنــایع در سیستـم‌هـای تولیــد، بهار و تابستان 1396، سال پنجم، شماره دهم، صفحـــه 67-23.
  • Pinedo (2008), Scheduling: Theory, Algorithms and Systems, Springer, New York, NY, USA, 3rd edition.
  • Low, C., Ji, M., Hsu, C.J., and Su, C.T. (2002) Minimizing the makespan in a single machine scheduling problem with flexible and periodic maintenance, Applied Mathematical Modelling, 34(2), pp. 334-342.
  • Mashkani, O., Moslehi, Gh., (2016) Minimising the total completion time in a single machine scheduling problem under bimodal flexible periodic availability constraints, International Journal of Computer Integrated Manufacturing, 29(3), pp. 1-19.
  • فرداد حمیدرضا و همکاران (1387)، ارایه یک روش صف‌بندی جدید برای انتقال ترافیک Diffserv روی شبکهRPR ، مهندسی برق مجلسی، پاییز 1387،دوره2، شماره 2، از صفحه 35 تا 43 .
  • Hermelin, D., (2018) Karhi, Sh., Pinedo, M., New algorithms for minimizing the weighted number of tardy jobs on a single machine, Ann Oper Res, published online.
  • M’Hallah, R., Bulfin, R., (2005) Minimizing the weighted number of tardy jobson a single machine with release dates, European Journal of Operational Research, 176, pp. 727–744.
  • Kramer, F., Lee, C., (1994) Due Window Scheduling for Parallel Machines, 20(2), pp. 69-89.
  • Anger F.D., Lee C.Y., and Martin-Vega L.A. (1986) Single machine scheduling with tight windows. Research Report, Department of Industrial and Systems Engineering, University of Florida.
  • Sidney, J.B., (1977) Optimal single machine scheduling with earliness and tardiness penalties, Operations Research, 25, 62–69.
  • Chang, P.C., Su, L.H., (2001) Scheduling n jobs on one machine to minimize the maximum lateness with a minimum number of tardy jobs, Computers &IndustrialEngineering40,349–360.
  • Briand, C., Ourari, S., (2011) Minimizing the number of tardy jobs for the singlemachine scheduling problem: MIP-based lower andupper bounds, RAIRO-OR.
  • B., (2007) Single machine rescheduling with new jobs arrivals and processing time compression, Int J Adv Manuf Technol,34: 378–384
  • Hall N.G. and C.N. Potts (2004), Rescheduling for new orders, Operations Research 52, 440-453.
  • Wu, C.C., and Lee, W.C., (2003) Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine, Information Processing Letters, 87(2), pp. 89-93.
  • Ming Liu, a., Feifeng Zhengb, c., Shijin Wanga, Jiazhen Huoa., (2012) Optimal algorithms for online single machine scheduling with deteriorating jobs, Theoretical Computer Science, 445, pp. 75-81.
  • Moore, J.M., “An n job, one machine sequencing algorithm for minimizing the number of late jobs”, Management Science, Vol., No., pp. 102-109, 1968.
  • Lenstra, J.K., Rinnooy, A.H.G. and P. Brucker, (1977) Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1, 343-362.
Journal of Industrial Engineering Research in Production Systems
Volume 9, Issue 18
September 2021
Pages 127-141

Files

Share

How to cite

Statistics