Job shop scheduling (or Job-shop problem) is an optimization problem in computer science and Operations Research in which ideal jobs are assigned to resources at particular times. The most basic version is as follows:
We are given n jobs J1, J2, ..., Jn of varying sizes, which need to be scheduled on m identical machines, while trying to minimize the makespan. The makespan is the total length of the schedule (that is, when all the jobs have finished processing). Nowadays, the problem is presented as an online problem (dynamic scheduling), that is, each job is presented, and the online algorithm needs to make a decision about that job before the next job is presented.
This problem is one of the most well known online problems, and was the first problem for which competitive analysis was presented, by Graham in 1966. Best problem instances for basic model with makespan objective are due to Taillard.
Read more about Job Shop Scheduling: Problem Variations, History, Major Results, Example
Famous quotes containing the words job and/or shop:
“Have windy words no limit? Or what provokes you that you keep on talking?”
—Bible: Hebrew, Job 16:3.
“The post-office appeared a singularly domestic institution here. Ever and anon the stage stopped before some low shop or dwelling, and a wheelwright or shoemaker appeared in his shirt- sleeves and leather apron, with spectacles newly donned, holding up Uncle Sam’s bag, as if it were a slice of home-made cake, for the travelers, while he retailed some piece of gossip to the driver, really as indifferent to the presence of the former as if they were so much baggage.”
—Henry David Thoreau (1817–1862)