Search

Each of N items (products) is to be processed on two machines in order to satisfy known demands in each of T periods. Only one item can be processed on each machine at any given time. Each switch from one item to another requires sequence dependent setup time. The object is to minimize the total set up time and the sum of the costs of production, backlog, storage and set up. In order to obtain the solution, we divide the above problem into two subproblems by introducing the hierarchy into the model. Because of this, we model the problem as a bilevel mixed 0-1 integer programming problem. The object of the leader is to assign the items to the machines in order to minimize the total setup time, while the object of the follower is to minimize the production, backlog, storage and setup cost of the machine. We develop a heuristics based on tabu search for solving the problem. At the end, some computational results are presented.

A model for real-time control of flexible manufacturing systems is considered. In this model, a machine can process a finite number of part types at specified rates, but only one part type can be processed at any given time. Each switch from one type to another requires setup time. The clear-the-largest-work-after-setup (CLWS) heuristic policy which stabilizes the system in the sense that, in the long run, the required demand is met, has been introduced. That way, a better upper bound on the total work backlog than those available in earlier literature is derived. Computational results for the case of finite horizon show that the error of the heuristic CLWS from the optimal solution is 2.5–3.0% on average. Some computational results that compare the CLWS heuristic to the heuristic available in the earlier literature, for the same problem, are also reported.

Each of N part types (production families or items) is to be processed on a single machine. The part types arrive into the buffer in front of the machine at every unit of time at specified rates. The machine can process a finite number of part types at specified rates, but only one part type can be processed at any given time. Each switch from one type to another requires setup time. The objective is to schedule the part types in the sense that the required demand is met and the average work backlog in the system is minimal. Assuming a finite horizon, we define this problem as mixed 0–1 programming problem. In order to strengthen the formulation, we consider its LP relaxation in an enlarged space of variables. By projecting this polyhedron into the space of the original variables we obtain new valid inequalities for the original problem that are then used as cutting planes in a cutting plane/branch and bound algorithm. At the end we report some computational results that have the objective of empirically estimating the reduction in the integrality gap (the gap between the optimal values of the original problem and its linear programming relaxation). Also, we give and compare the CPU times of the cutting plane/branch and bound algorithm proposed in this paper and the branch and bound algorithm applied directly to the original problem.