A new optimal algorithm for a time-dependent scheduling problem

• Autorzy: Kubale M. , Ocetkiewicz K. M.
• Języki publikacji: EN

Abstrakty

EN

In this article a single machine time-dependent scheduling problem with total completion time criterion is considered. There are n given jobs, j1,...,jn, and the processing time pi of the i-th job is given by pi = 1 + biSi, where si is the starting time of the i-th job, i = 1,...n. If all jobs have different and non-zero deterioration rates and bi [wzór], where bmin = min{bi}, then an optimal schedule can be found in O(n log n) time. The conducted computational experiments show that the presented algorithm performs very well even on data not satisfying the assumed constraints.

Słowa kluczowe

EN

scheduling; single machine; deteriorating jobs; total completion time; algorithms

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2009
• Tom: Vol. 38, no 3
• Strony: 713--721
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Kubale M.

autor

Ocetkiewicz K. M.

• Department of Algorithms and System Modeling, Gdańsk University of Technology, Gdańsk, ul. Gabriela Narutowicza 11/12, 80-233 Gdańsk Wrzeszcz, Poland,

Bibliografia

• BACHMAN, A. and JANIAK, A. (1997) Scheduling jobs with special type of start time dependent processing times. Wroclaw University of Technology, Report PRE 34/97.
• CHENG, T.C.E. and DING, Q. (2000) Single machine scheduling with deadlines and increasing rates of processing times. Acta Informatica 36 (9-10), 673-692.
• CHENG, T.C.E., DING, Q. and LIN, B.M.T. (2004) A concise survey of scheduling with time-dependent processing times European Journal of Operational Research 152, 1-13.
• GAWIEJNOWICZ, S. and PANKOWSKA, L. (1995) Scheduling jobs with varying processing times. Information Processing Letters 54, 175-178.
• GAWIEJNOWICZ, S., LAI, T.-C. and CHIANG, M.-H. (2000) Polynomially solvable cases of scheduling deteriorating jobs to minimize total completion time. In: Extended Abstracts of the 7-th Workshop on Project and Management Scheduling, 131-134.
• GAWIEJNOWICZ, S., KURC, W. and PANKOWSKA, L. (2002) A greedy approach for a time-dependent scheduling problem. LNCS 2328, Springer 79-86.
• GAWIEJNOWICZ, S. (2008) Time-Dependent Scheduling. Springer-Verlag, Berlin.
• GRAHAM, R.L., LAWLER, E.L., LENSTRA, J.K. and RINNOOY KAN, A.E.G. (1979) Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics 5, 287-326.
• MOSHEIOV, G. (1991) V-shaped policies for scheduling deteriorating jobs. Operations Research, 39 (6), 979-991.
• MOSHEIOV, G. (1994) Scheduling jobs under simple linear deterioration. Computers and Operations Research 21 (6), 653-659.