Scheduling is a key factor for manufacturing productivity. In a manufacturing environment scheduling is that allocates machines for processing a number of jobs. Proper and effective scheduling can cut lead times, improve on-time delivery, reduce inventory, and increase the reputation of enterprise. Recently, with the competitive pressure of today’s global market and consumer demand for variety, scheduling problem is becoming more and more important for the manufacturing industry.It is well-known that the Job Shop Problem is NP-hard, and the minimum Makespan problem of Job Shop scheduling is a classical combinatorial optimization problem. However, our theoretical understanding of these combinatorial optimizations is very limited, leading to significant problems for both researchers and practitioners. Specifically, the lack of a theory of problem impedes the development of more effective algorithms, prevents practitioners from identifying the algorithm most appropriate for a given problem.Based on analyzing combinatorial optimization and the model of JSP, we perform a novel analysis of the fitness landscapes of the Job Shop problem, prove that the JSP problem is very complexity; we research the configuration space of the JSP, trying to find the inherent characteristics of the Job Shop problem. Those results can provide theoretical basis for solving JSP. And on the basis, we give the methods framework to solving JSP. Those may provide a partial explanation for the remarkable success of the latter in solving the JSP.First, we introduced the general research methods of combinatorial optimization and the No Free Lunch theorem, and studied the fitness landscape of the knapsack problem and traveling salesman problem, and analyzed the global search. Then the relationship between fitness and the factors of impact of the fitness landscape space were analyzed. Second, the mathematical model and disjunction were given, and the complexity of this model was analyzed, and the characters of the fitness were studied, including the factors of impact of the Job Shop problem’s fitness landscape space were analyzed, followed it show that the landscape of the JSP is non-regular. Then the relation between the backbone and the fitness of the JSP is studied.Third, in order to using the landscape characters of the Job Shop to solve the problem, we also discuss the characters of evolution algorithm. In the process solving combinatorial optimization, we research the principle of crossover processing and mutation processing, and how those can impact the global optima. We get three typical fitness landscapes of the Job Shop problem, and we develop a general, fast and easily implemented hybrid optimization algorithm which base on Job Shop Problem Fitness Landscape and the particle swarm optimization;The effectiveness and efficiency of the proposed algorithm are demonstrated by applying it to some benchmark Job Shop scheduling problems. The effectiveness of the hybrid optimization algorithm model is also validated. One scheduling tool DAPSOJSP is developed.Finally, conclusion is drawn and the future research focus is pointed out.

News

April 3^rd, 2012: After a long incubation period, a new generation of the VirtualLabs is emerging: EvoLudo, a wiki based system that facilitates collaborative efforts to complement and augment research articles on evolutionary dynamics with interactive tutorials.

As of today a new tutorial on the Stochastic dynamics in finite populations is available on EvoLudo complementing a research article with Arne Traulsen and Jens-Christian Claussen in Phys. Rev. E 85 041901 doi: 10.1103/PhysRevE.85.041901.

Some of the VirtualLabs tutorials have already been revised, extended and migrated to EvoLudo and the remaining ones will follow in the near future. If you would like to get involved please contact me.

The first version of the VirtualLabs has been published in 2002, while I was working as a post-doctoral fellow with Karl Sigmund. Over the ten years the VirtualLabs have attracted almost 300’000 visitors. Now let’s take this to a new level with EvoLudo.

The VirtualLabs will remain available but no further updates to this site are planned in the near future. Please update your links and take advantage of the new and much more powerful java applets on EvoLudo.

Comments and suggestions are welcome.

—>

The best part of book tours are the questions. After spending years with the same ideas and sentences – they become old friends – it’s invigorating to see how people react, to keep track of which concepts spark their curiosity. It’s also fun to consider questions that never occured to me while writing the book. For instance, I was recently stumped by a seemingly obvious query that I hadn’t really considered. It was asked by a 4th grader: “What,” he wanted to know, “is the downside of creativity? Isn’t it possible that humans are too creative?”

via wired.com

bookworm arXiv

This guest article was written by author and consultant Tristan Yates (see his bio below). It emphasizes R’s data object manipulation and scoring capabilities via a detailed financial analysis example.

Scoring and ranking systems are extremely valuable management tools. They can be used to predict the future, make decisions, and improve behavior – sometimes all of the above. Think about how the simple grade point average is used to motivate students and make admissions decisions.

R is a great tool for building scoring and ranking systems. It’s a programming language designed for analytical applications with statistical capabilities. The capability to store and manipulate data in list and table form is built right into the core language.
 

But there’s also some validity to the criticism that R provides too many choices and not enough guidance. The best solution is to share your work with others, so in this article we show a basic design workflow for one such scoring and ranking system that can be applied to many different types of projects.

The Approach
For a recent article in Active Trader, we analyzed the risk of different market sectors over time with the objective of building less volatile investment portfolios. Every month, we scored each sector by its risk, using its individual ranking within the overall population, and used these rankings to predict future risk.

Here’s the workflow we used, and it can be applied to any scoring and ranking system that must perform over time (which most do):

1. Load in the historical data for every month and ticker symbol.
2. Load in the performance data for every month and ticker symbol.
3. Generate scores and rankings for every month and ticker symbol based upon their relative position in the population on various indicators.
4. Review the summary and look for trends.

In these steps, we used four data frames, as shown below:

Name	Contents
my.history	historical data
my.scores	scoring components, total scores, rankings
my.perf	performance data
my.summary	summary or aggregate data

 
One of my habits is to prefix my variables – it helps prevent collisions in the R namespace.

Some people put all of their data in the same data.frame, but keeping it separate reinforces good work habits. First, the historical data and performance data should never be manipulated, so it makes sense to keep it away from the more volatile scoring data.

Second, it helps draw a clear distinction between what we know at one point in time – which is historical data - and what we will know later – which is the performance data. That’s absolutely necessary for the integrity of the scoring system.

My.history, my.scores, and my.perf are organized like this:

yrmo	ticker	var1	var2	etc…
200401	XLF
200401	XLB
etc…

 
yrmo is the year and month and ticker is the item to be scored. We maintain our own list of dates (in yrmo format) and items in my.dates and my.items. Both these lists are called drivers, as they can help iterate through the data.frame, and we also have a useful data.frame called my.driver which has only the yrmo and ticker.

One trick – we keep the order the same for all of these data.frames. That way we can use indexes on one to query another. For example, this works just fine:

  Vol.spy <- my.history$vol.1[my.score$rank==1]

Loading Data
First, we get our driver lists and my.driver data.frame set up. We select our date range and items from our population, and then build a data.frame using the rbind command.

  #this is based on previous analysis
  my.dates <- m2$yrmo[13:(length(m2$yrmo)-3)]
  my.items <- ticker.list[2:10]

  #now the driver
  my.driver <- data.frame()
  for (z.date in my.dates) {
    my.driver <- rbind(my.driver,data.frame(ticker=my.items,yrmo=z.date))
  }

Next, let’s get our historical and performance data. We can make a function that can be called once for each row in my.driver that then loads any data needed.

  my.seq <- 1:length(my.driver[,1])
  my.history <- data.frame(ticker=my.driver$ticker,yrmo=my.driver$yrmo,
    vol.1=sapply(my.seq,calc.sd.fn,-1,-1))

Each variable can be loaded by a function called with the sapply command. The calc.sd.fn function first looks up the ticker and yrmo from my.driver using the index provided, and then returns the data. You would have one function for each indicator that you want to load. My.perf, which holds the performance data, is built in the exact same way.

The rbind command is slow unfortunately, but loading the historical and performance data only needs to be done once.

Scoring The Data
This is where R really shines. Let’s look at the highest level first.

  my.scores <- data.frame()
  for (z.yrmo in my.dates) {
    my.scores <- rbind(my.scores,calc.scores.fn(z.yrmo))
    }
  my.scores$p.tot <- (my.scores$p.vol.1)

Every indicator gets its own score, and then that can be combined in any conceivable way to create total score. In this very simple case, we’re only scoring one indicator, so we just use that score as the total score.

For more complex applications, the ideal strategy is to use multiple indicators from multiple data sources to tell the same story. Ignore those who advocate reducing variables and cross-correlations. Instead, think like a doctor that wants to run just one more test and get that independent confirmation.

Now the calc functions:

  scaled.score.fn <- function(z.raw)
    {pnorm(z.raw,mean(z.raw),sd(z.raw))*100}
  scaled.rank.fn <- function(z.raw) {rank(z.raw)}

  calc.scores.fn <- function(z.yrmo) {
    z.df <- my.history[my.history$yrmo==z.yrmo,]
    z.scores <- data.frame(ticker=z.df$ticker,yrmo=z.df$yrmo,
      p.vol.1=scaled.score.fn(z.df$vol.1),r.vol.1=scaled.rank.fn(z.df$vol.1))
    z.scores
    }

The calc.scores.fn function queries the data.frame to pull the population data for just a single point in time. Then, each indicator is passed to the scaled.score.fn and scaled.rank.fn function, returning a list of scores and ranks.

Here, we use the pnorm function to calculate a statistical Z-score, which is a good practice for ensuring that a scoring system isn’t dominated by a single indicator.

Checking the Scores
At this point, we create a new data.frame for summary analysis. We use the always useful and always confusing aggregate function and combine by rank. Notice how we easily we can combine data from my.history, my.scores and my.perf.

  data.frame(rank=1:9,p.tot=aggregate(my.scores$p.tot,
    list(rank=my.scores$r.vol.1),mean)$x,ret.1=aggregate(my.perf$ret.1,
    list(rank=my.scores$r.vol.1),mean)$x,sd.1=aggregate(my.perf$ret.1,
    list(rank=my.scores$r.vol.1),sd)$x,vol.1=aggregate(my.history$vol.1,
    list(rank=my.scores$r.vol.1),mean)$x,vol.p1=aggregate(my.history$vol.1,
    list(rank=my.scores$r.vol.1),mean)$x)

Here’s the result. We could check plots or correlations, but the trend – higher relative volatility in the past (vol.p1, p.tot) is more likely to mean higher relative volatility in the future (vol.1, sd.1) - is crystal clear.

rank	p.tot	ret.1	sd.1	vol.1	vol.p1
1	12.1	0.131	4.03	16.5	13.8
2	19.4	0.0872	4.82	16.6	16.1
3	27.1	0.2474	4.96	20.1	18
4	35.6	0.4247	5.31	20.9	19.9
5	44.9	0.6865	5.98	22.1	21.7
6	53	0.3235	5.84	21.5	23.2
7	65.1	1.019	5.86	24.6	25.4
8	78	0.7276	6.04	26.9	28.4
9	96.4	0.0837	9.34	35.2	38.3

 
In the case of our analysis, the scores aren’t really necessary – we’re only ranking nine items every month. If we did have a larger population, we could use code like this to create subgroups (six groups shown here), and then use the above aggregate function with the new my.scores$group variable.

  my.scores$group <- cut(my.scores$p.tot,
    breaks=quantile(my.scores$p.tot,(0:6)/6),include.lowest=TRUE,labels=1:6)

Wrap-up
We ultimately only ended up scoring one variable, but it’s pretty easy to see how this framework could be expanded to dozens or more. Even so, it’s an easy system to describe – we grade each item by its ranking within the population. People don’t trust scoring systems that can’t be easily explained, and with good reason.

There’s not a lot of code here, and that’s a testimony to R’s capabilities. A lot of housekeeping work is done for you, and the list operations eliminate confusing nested loops. It can be a real luxury to program in R after dealing with some other “higher level” language.

We hope you find this useful and encourage you to share your own solutions as well.

Tristan Yates is the Executive Director of Yates Management, a management and analytical consulting firm serving financial and military clients. He is also the author of Enhanced Indexing Strategies and his writing and research have appeared in publications including the Wall Street Journal and Forbes/Investopedia.