We consider a job-shop scheduling problem with n jobs (orders) and m machines. Each job-operation Oil (the l-th operation of job i, 1 ⩽ i ⩽ n, 1 ⩽ l ⩽ m) has a random time duration til with the average value &tmacr;il and the variance Vil. Each job has its priority index pi and its due date Di. The problem is to determine the starting time value Sil for each job-operation Oil. In our recent paper we solved that problem by introducing, at each decision point, a competition among the jobs ready to be served on one and the same machine. That competition is based on the idea of pairwise comparison. The main shortcoming of the developed model is that it does not deal with so-called ‘tense jobs’, i.e. with jobs that, in reality, may cause a bottleneck in the job-shop. This paper is a further extension of our previous publication. The newly developed model to determine Sil values is based on two alternative decision-making procedures in the case of a non-empty line for a certain machine: (A) To choose the winner of the competition for that machine. (B) To keep the machine idle until the ‘bottleneck’ job is ready to be served on that machine. Such a model is, in essence, a combination of the pairwise comparison and the ‘look ahead’ techniques which are modified for the case of random operations. The model provides an essential refinement of the job-shop's delivery performance versus the previous model. Extensive experimentation is undertaken to evaluate the efficiency of the model. .
