Search

This paper considers due date assignment and sequencing for multiple jobs in a single machine shop. The processing time of each job is assumed to be uncertain and is characterized by a mean and a variance with no knowledge of the entire distribution. A heuristic procedure is developed to find job sequence and due date assignment to minimize a linear combination of three penalties: penalty on job earliness, penalty on job tardiness, and penalty associated with long due date assignment. Numerical experiments indicate that the performance of the procedure is stable and robust to job processing time distributions. In addition, the performance improves when the means and variances of job processing times are uncorrelated or negatively correlated or when the penalty of a long due date assignment is significant.

In this paper, we consider the problem of providing flexibility to solutions of two-machine shop scheduling problems. We use the concept of group-scheduling to characterize a whole set of schedules so as to provide more choice to the decision-maker at any decision point. A group-schedule is a sequence of groups of permutable operations defined on each machine where each group is such that any permutation of the operations inside the group leads to a feasible schedule. Flexibility of a solution and its makespan are often conflicting, thus we search for a compromise between a low number of groups and a small value of makespan. We resolve the complexity status of the relevant problems for the two-machine flow shop, job shop and open shop. A number of approximation algorithms are developed and their worst-case performance is analyzed. For the flow shop, an effective heuristic algorithm is proposed and the results of computational experiments are reported.

We consider the two machine flow shop and open shop problems to minimize the weighted mean flow-time, processing times being equal to 0 or 1. The solution to the open shop problem is based on algorithms for the flow shop problem and the corresponding two parallel identical machine problem. For all problems O (n log n) algorithms are proposed.

A closed job shop system with a FIFO managed dispatch area is considered, under the assumption that the machine shop subsystem is constrained by an upper limit on the number of circulating jobs. An approach for the approximate solution of the nonproduct form queueing network model of the system is well established only for the case of a single class of jobs flowing through the system. In this paper we extend the previous approach to cover the case of multiple job classes. We combine hierarchical decomposition with the class aggregation technique, in order to obtain a practical approximate solution method. Class aggregation also enables to incorporate in our method the consolidated ‘exponentialization approach’. Hence the method also covers the case of machine centers having different and nonexponential service times per job class. The approximations developed are validated by simulation experiments.