We consider a job-shop manufacturing cell of n jobs (orders), Ji, 1⩽i⩽n, and m machines Mk, 1⩽k⩽m. Each job-operation Oiℓ (the ℓth operation of job i) has a random time duration tiℓ with the average value View the MathML source and the variance Viℓ. Each job Ji has its due date Di and the penalty cost Ci* for not delivering the job on time (to be paid once to the customer). An additional penalty View the MathML source has to be paid for each time unit of delay, i.e., when waiting for the job's delivery after the due date. If job Ji is accomplished before Di it has to be stored until the due date with the expenses View the MathML source per time unit.
The problem is to determine optimal earliest start times Si of jobs Ji, 1⩽i⩽n, in order to minimize the average value of total penalty and storage expenses. Three basic principles are incorporated in the model:
1. At each time moment when several jobs are ready to be served on one and the same machine, a competition among them is introduced. It is based on the newly developed heuristic decision-making rule with cost objectives.
2. A simulation model of manufacturing the job-shop and comprising decision-making for each competitive situation, is developed.
3. Optimization is carried out by applying to the simulation model the coordinate descent search method. The variables to be optimized are the earliest start times Si.
Table options
A numerical example of a simulation run is presented to clarify the decision-making rule. The optimization model is verified via extensive simulation.
It can be well-recognized from recent publications [1], [2], [3], [4], [5], [6] and [7] that optimal analytical models can be applied only to specific cases in job-shop and flow-shop scheduling with random operations. As for general job-shop problems with random operations, optimization problems have not obtained an analytical solution. Our recent publications [8] and [9] consider general job-shop manufacturing cells with random operations. The results obtained center on suggesting heuristic decision-making rules in situations when several jobs are ready to be served on one and the same machine and the problem is to choose one of the competitive jobs to be passed to that machine. But in these publications, we have not considered optimization problems. Only non-cost parameters (total time to accomplish all the jobs, probabilities for each job to meet its due date on time, etc.) have been used in the models.
This publication is an essential development of our previous papers [8] and [9].
We consider a job-shop manufacturing cell of n jobs (orders), Ji, 1⩽i⩽n, and m machines Mk, 1⩽k⩽m. Each job-operation Oiℓ (the ℓth operation of job i) has a random time duration tiℓ with the average value View the MathML source and the variance Viℓ. Each job Ji has its due date Di and the penalty cost Ci* for not delivering the job on time (to be paid once to the customer). An additional penalty View the MathML source has to be paid for each time unit of delay, i.e., when waiting for the job's delivery after the due date. If job Ji is accomplished before Di it has to be stored until the due date with the expenses View the MathML source per time unit storage.
The problem is to determine optimal earliest times Si, 1⩽i⩽n, to start processing jobs Ji, in order to minimize the average value of total penalty and storage expenses.
In order to solve the problem, we have developed a new decision-making rule for choosing a job from the line. The rule is, in essence, a combination of the pairwise comparison model for stochastic job-shop scheduling outlined in [8] and the cost objective calculated for the competitive pair of jobs. Developing the decision-making rule enables a job-shop's simulation model by random sampling of the actual job-operation's time durations. By simulating the manufacturing cell many times, the average value of the total penalty and storage expenses can be evaluated. Note that the average expenses value depends on values Si, 1⩽i⩽n. This, in turn, enables application of one of the approximate search methods [7] in order to determine optimal values Si to minimize the average expenses. We have chosen the cyclic coordinate descent algorithm which minimizes the cost objective cyclically with respect to the coordinate variables. The algorithm is easy to use and can be applied to any kind of non-linear multidimensional problems. The algorithm has been successfully used in various production and scheduling problems, e.g. in [11].
The developed optimization model can be used for job-shop manufacturing cells with random operations and various cost penalties and expenses. Similar studies by other authors have not been published elsewhere.
The structure of the paper is as follows. In Section 2, we present the system description, while Section 3 considers a notation and the problem formulation. In Section 4, we consider the idea of the pairwise comparison, while Section 5 presents the decision-making rule for two competitive jobs with a cost objective. In Section 6, the coordinate descent method to solve the optimization problem is outlined, while Section 7 presents a numerical example of a simulation run. In Section 8, extensive experimentation based on computer usage will be undertaken. Section 9 presents conclusions and suggests future research.
1. The newly developed optimization model for a general job-shop problem with a cost objective enables an efficient solution to be obtained: using two cyclic iterations results in decreasing the average job-shop storage and penalty expenses by 94–96 per cent.
2. We are unable to compare the optimization model with other results in that area since similar research has not yet been published elsewhere.
3. The optimization algorithm is simple in use and can be implemented on a PC. It can be applied for static job-shop problems with cost parameters and with a given set of jobs available at the same time, with no new jobs joining the job-shop, and no due date changing during the completion of the originally available jobs.
4. A combination of earliest start times with a cost-minimization decision rule makes sense as a realistic heuristic. However, in job-shop scheduling, there are often many more different decisions to make besides the earliest starts of the jobs, e.g., the determination of delivery times for all machines to begin the manufacturing process, etc. Thus, other decision-makings may be incorporated in the model in future research.
5. Considering storage cost penalty, under certain assumptions, makes economic sense. In the case of high machine utilization, the holding cost is small relative to the cost of unused production capacity. However, for low machine utilization, deliberate delay of finishing the job may be more economic.
6. In summary, the problem presented in this paper has the potential of opening new directions for future research in job-shop scheduling.
