BazEkon - Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie

BazEkon home page

Meny główne

Autor
Barketau Maksim S. (Belarus State University, Belarus; The Hong Kong Polytechnic University, China; National Academy of Sciences of Belarus, Belarus), Cheng T.C. Edwin (Hong Kong Polytechnic University, China), Kovalyov Mikhail Y. (Belarus State University, Belarus), Ng C.T. Daniel (Hong Kong Polytechnic University, China)
Tytuł
Batch Scheduling of Deteriorating Products
Źródło
Decision Making in Manufacturing and Services, 2007, vol. 1, nr 1/2, s. 25-34, bibliogr. 9 poz.
Słowa kluczowe
Maszyny i urządzenia, Planowanie operacyjne, Czas pracy, Algorytmy
Machinery and equipment, Operational planning, Working time, Algorithms
Uwagi
summ.
Abstrakt
In this paper we consider the problem of scheduling N jobs on a single machine, where the jobs are processed in batches and the processing time of each job is a simple linear increasing function depending on job's waiting time, which is the time between the start of the processing of the batch to which the job belongs and the start of the processing of the job. Each batch starts from the setup time S. Jobs which are assigned to the batch are being prepared for the processing during time S0 < S. After this preparation they are ready to be processed one by one. The non-negative number bi is associated with job i. The processing time of the i-th job is equal to bi(si - (sib + S0)), where sib and si are the starting time of the b-th batch to which the i-th job belongs and the starting time of this job, respectively. The objective is to minimize the completion time of the last job. We show that the problem is NP-hard. After that we present an O(N) time algorithm solving the problem optimally for the case bi = b. We further present an O(N2) time approximation algorithm with a performance guarantee 2.(original abstract)
Pełny tekst
Pokaż
Bibliografia
Pokaż
  1. Al-Anzi F.S., Allahverdi A., Kovalyov M.Y., Batching Deteriorating Items with Applications in Computer Communication and Reverse Logistics, European Journal of Operational Research, accepted 2007.
  2. Barketau M.S., Cheng T.C.E., Kovalyov M.Y., Ng C.T.D., Computational complexity of "Product Partition" and related problems, working paper 2007.
  3. Beckenbach E.F., Bellman R., Inequalities, Springer-Verlag, New-York 1971.
  4. Browne S., Yechiali U., Schedulinng deteriorating jobs on a single processor, Operations Research, 38 (1990), 495-498.
  5. Cheng T.C.E., Ding Q., Single machine scheduling with step-deterioration processing times, European Journal of Operational Research, 134 (2001), 623-630.
  6. Cheng T.C.E., Ding Q., Lin B.M.T., A concise survey of scheduling with time-dependent processing times, European Journal of Operational Research, 152 (2004), 1-13.
  7. Garey M.R., Johnson D.S., Computers and intractability: A guide to the Theory of NP-Completeness. Freeman, New York 1979.
  8. Mosheiov G., V-Shaped policies for scheduling deteriorating jobs, Operations Research, 39 (1992), 6, 979-991.
  9. Mosheiov G., Scheduling jobs under simple linear deterioration, Computers and Operations Research, 21 (1994), 6, 653-659.
Cytowane przez
Pokaż
ISSN
2300-7087
Język
eng
URI / DOI
http://dx.doi.org/10.7494/dmms.2007.1.2.25
Udostępnij na Facebooku Udostępnij na Twitterze Udostępnij na Google+ Udostępnij na Pinterest Udostępnij na LinkedIn Wyślij znajomemu