problem. Every job consists of operations for . The operations can be scheduled in any order. Operation must be processed for units on machine . F: Flow-shop problem. Every job consists of operations for , to be scheduled in the given order. Operation must be processed for units on machine . J: Job-shop problem. Every job consists of operations for , to be scheduled in that order. Operation must be processed for units on a dedicated machine with for . Job characteristics All processing times are assumed to be integers. In some older research papers however they are assumed to be rationals. , or : the processing time is equal for all jobs. , or : the processing time is equal to 1 time-unit for all jobs. : for each job a release time is given before which it cannot be scheduled, default is 0. : an online problem. Jobs are revealed at their release times. In this context the performance of an algorithm is measured by its competitive ratio. : for each job a due date is given. The idea is that every job should complete before its due date and there is some penalty for jobs that complete late. This penalty is denoted in the objective value. The presence of the job characteristic is implicitly assumed and not denoted in the problem name, unless there are some restrictions as for example , assuming that all due dates are equal to some given date. : for each job a strict deadline is given. Every job must complete before its deadline. pmtn: Jobs can be preempted and resumed possibly on another machine. Sometimes also denoted by 'prmp'. : Each job comes with a number of machines on which it must be scheduled at the same time. The default is 1. This is an important parameter in the variant called parallel task scheduling. Precedence relations Precedence relations might be given for the jobs, in form of a partial order, meaning that if i is a predecessor of i′ in that order, i′ can start only when i is completed. prec: Given general precedence relation. If then starting time of should be not earlier than completion time of . chains: Given precedence relation in form of chains (indegrees and outdegrees are at most 1). tree: Given general precedence relation in form of a tree, either intree or outtree. intree: Given general precedence