language-icon Old Web
English
Sign In

Job shop scheduling

Job shop scheduling or the job-shop problem (JSP) is an optimization problem in computer science and operations research in which 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 processing times, which need to be scheduled on m machines with varying processing power, while trying to minimize the makespan. The makespan is the total length of the schedule (that is, when all the jobs have finished processing). Job shop scheduling or the job-shop problem (JSP) is an optimization problem in computer science and operations research in which 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 processing times, which need to be scheduled on m machines with varying processing power, while trying to minimize the makespan. The makespan is the total length of the schedule (that is, when all the jobs have finished processing). The standard version of the problem is where you have n jobs J1, J2, ..., Jn. Within each job there is a set of operations O1, O2, ..., On which need to be processed in a specific order (known as Precedence constraints). Each operation has a specific machine that it needs to be processed on and only one operation in a job can be processed at a given time. A common relaxation is the flexible job shop where each operation can be processed on any machine (the machines are identical). This problem is one of the best known combinatorial optimization 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. The name originally came from the scheduling of jobs in a job shop, but the theme has wide applications beyond that type of instance.

[ "Scheduling (computing)", "Utility model", "Scheduling (procedure)", "Flow shop scheduling", "job rejection", "Rate-monotonic scheduling", "batch machine" ]
Parent Topic
Child Topic
    No Parent Topic