|
...single machine scheduling problem with sequence-dependent setup times. This reduced problem can transformed into a Traveling Salesman Problem (TSP), which can be efficiently solved using Little's method. In the second part, a feasible initial solution to the original problem is obtained by exploiting the results of the first part. This initial solution is then improved in a step by step manner, taking into account the setup times and job splitting. We develop a lower bound and evaluate the performances of our heuristic on a large number of r simplicity and its efficiency.
3. Problem description
In our problem, N jobs indexed from one to N must be scheduled on M identical machines indexed from one to M. A job can be split into sections and any section can be processed by any one of the machines. However, when a machine switches the production from a job i (i = 1, 2,...,N) to a job] j (j = 1,2,...,N, j [not equal to] i), a setup time [S.sub.i,j] [greater than or equal to] is required. Without loss of generality, we set [S.sub.i,i] = (i = 1, 2,..., N). The processing time of job i (i = 1, 2,...,N) is given by [p.sub.i] > 0. The decision consists of specifying [Q.sub.i,m], the length of the section of job i (i = 1, 2,...,N) to be processed on machine m (m = 1, 2,..., M) so that
[summation over (M/m=1)] [Q.sub.i,m] = [p.sub.i], for any i = 1, 2,...,N, (1)
and, for each machine, determining in which order the job sections must be processed. In theory, more than one part of the same job is allowed to be processed by a machine. However, this possibility does not lead to a better solution, as we will show in the next section. Therefore, there is at most one part of each job on a machine.
If [C.sub.i] denotes the completion time of job i (to be decided) i.e., the completion time of the last finished fraction of job i, the criterion is to
Minimize [C.sub.max] = [max.sub.l[less than or equal to]i[less than or equal to]N] [C.sub.i].
Let [D.sub.m] denote the time at which machine m (m = 1, 2,...,M) finishes processing, called the finishing time, our criterion is equivalent to minimizing
[C.sub.max] = [max.sub.1[less than or equal to]m[less than or equal to]M] [D.sub.m].
Note that [D.sub.m] is the sum of the total length of the jobs assigned to machine m and the sum of the setup times. The first term does not depend on the order in which the jobs are processed, which, however, is not the case for the second term.
We assume that if a part of a job is scheduled at the beginning of the schedule, no setup time is needed. This is the case where a schedule is computed for a given horizon. When a schedule is completed, all machines undergo preventive maintenance. During the preventive maintenance, the machines are also setup to the next desired state. With this assumption, by introducing a dummy job, job 0, we have [S.sub.0,j] = and [S.sub.j,0] = 0.
Furthermore, we assume that the setup times verify the triangle property; that is, for any three different jobs i, j and k (i, j, k = 1, 2,...,N), we have [S.sub.i,j] + [S.sub.j,k] [greater than or equal to] [S.sub.i,k]. This assumption is not restrictive, since otherwise, instead of changing directly from the processing of job i to that of job k, we might introduce an intermediate job j.
4. Analytical properties
The problem described in Section 3 exhibits interesting properties. These properties are stated in this section.
Property 1. There is at least one optimal solution such that at most one part of any job is processed by the same machine.
Proof. Assume that there is an optimal solution in which more than one part of a job i is processed by some machine m. Let a and b be the job preceding and the job following the second part of job i, respectively. We construct a new schedule in which the first two parts of job i are reassembled to form a single section and the relative processing order of other parts remains the same. In this new schedule, [D.sub.m] does not increase, because the time devoted to setups are reduced by [S.sub.a,i] + [S.sub.a,b] [greater than or equal to] 0, due to the triangle property.
Property 2. If [Q.sub.i,m] (i = 1, 2,...,N, m = 1, 2,...,M) is specified, then the problem can be decomposed into M sub-problems independent one of another and each subproblem is equivalent to a Traveling Salesman Problem (TSP).
Proof. When [Q.sub.i,m] (i = 1, 2,...,N, m = 1, 2,...,M) is specified, machines can be scheduled independently, since individual sections can be considered as independent jobs and no precedence constraint exists between machines. The objective function can also be decomposed into M independent terms, each corresponding to exactly one machine.
The problem corresponding to each machine consists of scheduling jobs assigned to the considered machine to minimize the time at which the last part is completed. This is equivalent to a single machine scheduling problem with setup times to minimize makespan. This problem has been shown to be equivalent to a Traveling Salesman Problem (TSP) with the cities of the TSP corresponding to jobs with a strictly positive length assigned to the considered machine. The distances between cities correspond to the setup times between jobs. There is an additional city corresponding to the beginning of the schedule. The distance from this city to any other and that from any other city to this one are equal to zero. The processing sequence of jobs is given by the order in which the cities are visited.
Property 3. Let [C.sup.(1)] be the minimal makespan in case that M = 1. Then [C.sup.(1)] / M is an upper bound for the M-machine problem.
Proof. Consider the optimal schedule corresponding to the single machine problem. Divide the schedule into M equal parts. Each part can be executed on one of the M machines by eliminating the beginning and/or the end if they corresponds to a setup, since no setup is needed at the beginning or at the end of a machine. The M-machine schedule obtained in this way is feasible and the make span is at most [C.sup.(1)] / M.
These theoretical properties allow us to develop a heuristic algorithm described in Section 6.
5. A lower bound
The development of the lower bound requires a lemma that must be proved first.
Lemma 1. Let w be the optimal value of the objective function of the following minimization problem
Minimize [summation over (q/k=1)] [c.sub.k][u.sub.k],
subject to
[u.sub.k] + [y.sub.k] [greater than or equal to] 1, k = 1,2,...,q, (2)
[summation over (q/k=1)] [y.sub.k] [less than or equal to] r; (3)
[u.sub.k],[y.sub.k] [member of] N,k = 1,2,...,q,
where N the set of natural numbers, r [member of] N, r [less than or equal to] q, [less than or equal to] [c.sub.1] [less than or equal to] [c.sub.2] [less than or equal to] ... [less than or equal to] [c.sub.q]. Then, we must have
w = [summation over (q-r/k=1)] [c.sub.k].
Proof. We show that the following solution denoted as [sigma] is optimal: [u.sub.k] = 1, [y.sub.k] = 0, for any k = 1,2,...,q - r and [u.sub.k] = 0, [y.sub.k] = 1 for any k = q - r + 1,...,q.
It is easy to check that this solution is feasible. The optimality of solution [sigma] can be justified as follows. Considering the objective function, the smaller the value of the [u.sub.k]'s, the better the solution will be. The smallest value for a [u.sub.k] is zero. Due to constraints (2), each time a [u.sub.k] is set to zero, we must have [y.sub.k] [greater than or equal to] 1. Taking into account constraint (3), there are at most r values of k such that [y.sub.k] = 1 and hence [u.sub.k] can be set to...
NOTE: All illustrations and photos
have been removed from this article.
Looking for additional articles?
Search our database of over 3 million articles.
Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication
name or publication date.
About Goliath
Whether you're looking for sales prospects, competitive information, company
analysis or best practices in managing your organization,
Goliath can help you meet your business needs.
Our extensive business information databases empower business
professionals with both the breadth and depth of credible,
authoritative information they need to support their business
goals. Whether it be strategic planning, sales prospecting,
company research or defining management best practices -
Goliath is your leading source for accurate information.
|
