Abstract
This article discusses the problem of scheduling a large set of parts on an FMS so as to minimize the total completion time. Here, the FMS consists of a set of parallel identical machines. Setup time is incurred whenever a machine switches from one type of part to another. The setup time may be large or small depending on whether or not the two part types belong to the same family. This article describes a fast heuristic for this scheduling problem and derives a lower bound on the optimal solution. In computational tests using random data and data from an IBM card test line, the heuristic archieves nearly optimal schedules.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Coffman, E.G., Garey, M.R., and Johnson, D.S., “An Application of Bin-Packing to Multiprocessor Scheduling,” SIAM Journal of Computing, Vol. 7, pp. 1–16 (1978).
Dietrich, B.L. “A Two Phase Heuristic for Scheduling on Parallel Unrelated Machines with Set-ups,” RC 14330, IBM T.J. Watson Research Center, Yorktown Heights, NY (1989).
Geoffrion, A.M. and Graves, G.W. “Scheduling Parallel Production Lines with Changeover Costs: Practical Application of a Quadratic/LP Approach,” Operations Research, Vol. 24, pp 595–610 (1976).
Graham, R.L., “Bounds on Multiprocessing Timing Anomalies” SIAM Journal of Applied Mathematics, Vol. 17, pp. 416–429 (1969).
Hochbaum, D.S. and Shmoys, D.B., “Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results,” Journal of the Assoc. for Computing Machinery, Vol. 34, No. 1, pp. 144–162 (1987).
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., and Shmoys, D.B., The Traveling Salesman Problem, John Wiley, New York (1985).
Tang, C.S., “Scheduling Batches on Flexible Manufacturing Machines”, To appear in European Journal of Operational Research
Tang, C.S. and Wittrock, R.J., “Parallel Machine Scheduling with Major and Minor Setups”, RC 11412, IBM T.J. Watson Research Center, Yorktown Heights, NY (1985).
Ullman, J.D., “Complexity of Sequencing Problems,” in Computer and Job/Shop Scheduling Theory, E.G. Coffman (Ed.), John Wiley, New York, pp. 139–164 (1976).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Wittrock, R.J. Scheduling parallel machines with major and minor setup times. Int J Flex Manuf Syst 2, 329–341 (1990). https://doi.org/10.1007/BF00186472
Issue Date:
DOI: https://doi.org/10.1007/BF00186472