I have a job shop scheduling problem with the following characteristics. How would I write that in alpha|beta|gamma notation (see 1,2)? I know some of the parts, but not all. I add my suggestions in code blocks.


  • Job shop J
  • number of machines is part of the input m


  • batch processing b with job compatibilities ? and capacity constraints ? (i.e., a machine can process multiple jobs, if they belong to the same family and the machines capacity suffices. Each job has a fixed resource allocation which is the same on every machine.)
  • release times r_j
  • non-uniform setup times, depending on the schedule ?
  • transportation delays between machines, depending on the job and the machine t_{j,k}


  • minimizing total completion times sum(C_j)

Further: Is it true, that the job-shop implies a strict ordering of the jobs, so a precedence relation is implicit, or should i note that as well? In my problem, the jobs have to be processed by machines in the given order. (Btw.: The "direction" defines the compatibility.)


  • Job 1: machines {1, 2, 3, 4}, comp. class A
  • Job 2: machines {3, 4, 5}, comp. class A
  • Job 3: machines {6, 5, 4, 3}, comp. class B

(Edit: Add links to sources about the notation.)



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.