Job shop scheduling with unit length tasks

DOI10.1051/ITA/2011132MaRDI QIDQ2905324zbMATH OpenOpenAlexFDO

Authors Raphael Bernhard, Meike Akveld

Publication date 27 August 2012

Published in RAIRO. Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=ITA_2012__46_3_329_0/, https://eudml.org/doc/221998

zbMATH Keywords

competitive analysisjob shop schedulingonline algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27) Stochastic scheduling theory in operations research (90B36)

Review text

In the job shop scheduling problem a set of jobs, each consisting of a group of tasks, needs to be scheduled on a group of machines to minimize the maximum completion time, or makespan. Each task requires the use of a particular machine for a predetermined amount of time. The paper considers the online version of the problem with 2 jobs and tasks of unit length. In the online version of the job shop scheduling problem, the tasks of a job are not specified at the beginning, but disclosed to the algorithm one at a time. For each task the online algorithm must make an irrevocable decision as to where the task is to be scheduled.NEWLINENEWLINEThe paper presents a very simple deterministic algorithm with asymptotic competitive ratio 1 for the case when one of the jobs has at least twice as many tasks as the other one. The authors also give a simple randomized online algorithm with expected asymptotic competitive ratio 1 for the case when the above condition on the number of tasks of the jobs is not satisfied. Finally, a randomized online algorithm with expected asymptotic competitive ratio 1 is also presented for the case of 3 jobs, each having the same number of tasks.

Recommendations

• Job shop scheduling with unit length tasks: bounds and algorithms
• scientific article; zbMATH DE number 2044495
• On the power of randomization for job shop scheduling withk-units length tasks
• Job shop scheduling with unit processing times
• Job Shop Scheduling with Unit Processing Times

Cites work

• Advice complexity and barely random algorithms
• An efficient algorithm for the job-shop problem with two jobs
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 2114378 (Why is no real title available?)
• Job shop scheduling with unit length tasks: bounds and algorithms
• On the Advice Complexity of Online Problems

Cited in

(8)

• Job shop scheduling with deadlines
• Scheduling unit-length jobs with machine eligibility restrictions
• Job shop scheduling with unit processing times
• Advice complexity of fine-grained job shop scheduling
• On the power of randomization for job shop scheduling withk-units length tasks
• scientific article; zbMATH DE number 2044495 (Why is no real title available?)
• scientific article; zbMATH DE number 1775452 (Why is no real title available?)
• Job shop scheduling with unit length tasks: bounds and algorithms

This page was built for publication: Job shop scheduling with unit length tasks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2905324)