Skip to main content

Is there a way to ignore some machines (set to nothing) in job shop scheduling problem?

I am working on a job scheduling program with the objective of reducing makespan that involves scheduling multiple jobs on multiple machines, where:

  1. The same job cannot operate on different machines at the same time
  2. Only one job can process at a given time on a given machine

However, I'd like to add a constraint that some machines may not be needed to process a particular job. As shown below, for the list of machine elements, job 1 can occur on machine 0 and 2, but doesn't need to go through machine 1 (it can skip this machine). To designate the null, I added np.nan. (Note: If you insert either 0, 1, or 2 here in place of np.nan, this entire code will run without errors.)

Here is my code so far:

from pulp import *
import pandas as pd
import numpy as np
import collections as cl
from itertools import product

# define model
schedule = LpProblem(name="Minimize_Schedule", sense=LpMinimize)

# define number of machines (m) and jobs (n)
m = 3
n = 3

# for each job, the processing time of each
times = [[2, 1, 2],
         [1, 2, 2],
         [1, 2, 1]]

# for each job, the order the machines will go in
# for job 1, machine 1 is not needed
machines = [[0, np.nan, 2],
            [1, 2, 0],
            [2, 1, 0]]

# variables

# objective function to minimize (the makespan)
c = LpVariable(name="C")
# starting time x, on job j (from all jobs n) on machine i (from all machines m)
x = [[LpVariable(name='x({} ,{} )'.format(j+1, i+1), lowBound=0) for i in range(m)] for j in range(n)]
# y is a binary, where 1, if job j precedes job k on machine i; else 0
y = [[[LpVariable(name='y({} ,{} ,{} )'.format(j+1, k+1, i+1), cat="Binary") for i in range(m)] for k in range(n)] for j in range(n)]

# sum of total time for all machines (m) and jobs (n)
M = sum(times[i][j] for i in range(n) for j in range(m))

# add objective function to schedule model
schedule += c

# job j can only begin after job i has been completed
for (j, i) in product(range(n), range(1, m)):
    schedule += x[j][machines[j][i]] - x[j][machines[j][i-1]] >= times[j][machines[j][i-1]]

# same jobs cannot occur at same time
for (j, k) in product(range(n), range(n)):
    if k != j:
        for i in range(m):
            schedule += x[j][i] - x[k][i] + M*y[j][k][i] >= times[k][i]
            schedule += -x[j][i] + x[k][i] - M*y[j][k][i] >= times[j][i] - M
        
   
for j in range(n):
    schedule += c - x[j][machines[j][m-1]] >= times[j][machines[j][m-1]]

status = schedule.solve()

print(f"status: {schedule.status}, {LpStatus[schedule.status]}")
print("Completion time: ", schedule.objective.value())

for i,j in product(range(m),range(n)):
    if x[i][j].varValue >= 0:
        print("job %d starts on machine %d at time %g" % (i+1, j+1, x[i][j].varValue))

But I'm running into an error at this line:

# job j can only begin after job i has been completed
for (j, i) in product(range(n), range(1, m)):
    schedule += x[j][machines[j][i]] - x[j][machines[j][i-1]] >= times[j][machines[j][i-1]]

Which says:

TypeError: list indices must be integers or slices, not float

Is it not possible to insert a missing value into the machine list for this type of Mixed Integer program? Or will a simple update to this line of code suffice?

As another attempt, I tried to add None instead of np.nan and this returned the error:

TypeError: list indices must be integers or slices, not NoneType


source https://stackoverflow.com/questions/70352814/is-there-a-way-to-ignore-some-machines-set-to-nothing-in-job-shop-scheduling-p

Comments

Popular posts from this blog

Why is my reports service not connecting?

I am trying to pull some data from a Postgres database using Node.js and node-postures but I can't figure out why my service isn't connecting. my routes/index.js file: const express = require('express'); const router = express.Router(); const ordersCountController = require('../controllers/ordersCountController'); const ordersController = require('../controllers/ordersController'); const weeklyReportsController = require('../controllers/weeklyReportsController'); router.get('/orders_count', ordersCountController); router.get('/orders', ordersController); router.get('/weekly_reports', weeklyReportsController); module.exports = router; My controllers/weeklyReportsController.js file: const weeklyReportsService = require('../services/weeklyReportsService'); const weeklyReportsController = async (req, res) => { try { const data = await weeklyReportsService; res.json({data}) console...

How to show number of registered users in Laravel based on usertype?

i'm trying to display data from the database in the admin dashboard i used this: <?php use Illuminate\Support\Facades\DB; $users = DB::table('users')->count(); echo $users; ?> and i have successfully get the correct data from the database but what if i want to display a specific data for example in this user table there is "usertype" that specify if the user is normal user or admin i want to user the same code above but to display a specific usertype i tried this: <?php use Illuminate\Support\Facades\DB; $users = DB::table('users')->count()->WHERE usertype =admin; echo $users; ?> but it didn't work, what am i doing wrong? source https://stackoverflow.com/questions/68199726/how-to-show-number-of-registered-users-in-laravel-based-on-usertype

The number of nodes and edges I calculated manually and by a method provided by networkx library dont match

I am trying to analyse a graph using networkx library in Python. I have implemented a function that returns the nodes and edges of that graph. After that I counted the number of nodes and edges by implementing the len() function for nodes and edges, which gave me 17 for both nodes and edges. However, when I used the method graph.number_of_nodes() of networkx library it gave me 53. My code: import pandas as pd import networkx as nx import matplotlib.pyplot as plt header_list = ["a","b","w"] E =pd.read_csv("aves-barn-swallow-contact-network.edges",sep=" ",header= None,names=header_list) # print(E.head()) # prints first few rows of the csv file G = nx.from_pandas_edgelist(E,"a","b",["w"]) nx.draw(G) plt.show() class GraphAnalyse: #finding nodes and edges def nodeEdge(self,Graph): nodes = Graph.nodes() edges = Graph.edges() ...