Job Shop Schedule Problem

Answered

JUN ZHOU

• September 25, 2024 05:32

Hi all,

I'm considering a job shop shceduling problem, as shown in the following figure. In this example, there are three printed paper products that must pass through color printing presses in a particular order. The given data consists of a flowsheet showing the order in which each job passes through the color presses. But I don't know how to add the no overlap constraint, e.g, bule printer can't process two tasks at the same time. Could you please give me some advice?

Thanks a lot for your help.

Related to

• JobShop

0

• 

  Riley Clement

  Gurobi Staff

  • September 25, 2024 05:39
  • Edited

  Hi Jun Zhou,

  This problem is called Job Shop Scheduling.  Check out the following paper for several ways this can be modeled:

  Ku, Wen-Yang, and J. Christopher Beck. "Mixed integer programming models for job shop scheduling: A computational analysis." Computers & Operations Research 73 (2016): 165-173.

  - Riley

   

  0
• 

  JUN ZHOU

  • September 25, 2024 05:42

  

  

  

  Hi Riley,

  Thanks for your suggestions. I'll check the paper.

  0
• 

  JUN ZHOU

  • September 26, 2024 04:39

  

  

  

  Hi Riley,

  Thanks for your help. I have solved the Job-Shop Scheduling Problem. May I know whether Gurobipy can solve Flexible Job-Shop Scheduling problem? The idea is nearly the same. I think it shoule be able do this. 

  0
• 

  Riley Clement

  Gurobi Staff

  • September 26, 2024 04:54

  Hi Jun Zhou,

  Technically speaking no,  Gurobi doesn't solve the Flexible Job-Shop Scheduling problem, but it doesn't solve the Job-Shop Scheduling problem, or routing problems, or planning problems, or resource allocation problems etc, either.  It solves LPs, MILP, QPs, QCPs, MIQCPs and so on.  If a modeller can transform their problem, such as the Flexible Job-Shop Scheduling problem, into one of these problems that Gurobi can solve, then then it can make sense to use Gurobi.

  There look to be some MILP formulations for the Flexible Job-Shop Scheduling problem in this paper:

  Gomes*, M. C., A. P. Barbosa-Povoa, and A. Q. Novais. "Optimal scheduling for flexible job shop operation." International journal of production research 43.11 (2005): 2323-2353

  - Riley

   

   

  0
• 

  JUN ZHOU

  • September 26, 2024 05:01

  

  

  

  Thanks for your prompt response, Riley. I'll check the paper. I'll try to formulate the flexible job shop scheduling problem into MILP. Thanks again.

  0
• 

  Riley Clement

  Gurobi Staff

  • September 26, 2024 05:02

  No problem, best of luck!

  0

Please sign in to leave a comment.