Order selection on a single machine with high set-up costs
type: Item
instance of: scholarly article
title: Order selection on a single machine with high set-up costs
zbMATH Open document ID: 0797.90035
DOI: 10.1007/BF02024936
author: Brenda L. Dietrich
author: Jon Lee
author: Thomas Lee
published in: Annals of Operations Research
publication date: 1993-12-20T00:00:00Z
review text: A single resource is used to produce a number of different part-types. A large set-up cost is incurred when switching the resource from one part- type to another, but the per item cost for each part-type is small. As a result, it is economical to produce only large batches of each part-type. Customer orders require one or more part-types. Revenue is received for an order only if it is completely filled. The goal is to maximize short- term profit. It is assumed that resource availability during the ``short- term planning horizon'' is not sufficient to produce all of the orders. Then, to optimize short-term profit, one must select the most profitable set of orders that can feasibly be produced. This problem is formulated as an integer linear program. Then the authors consider an approximation to this model which is more amenable to the solution techniques of mixed-integer programming. They present a heuristic for the solution of this problem. The heuristic performs quite will on randomly generated test problems. The heuristic is also used to provide good lower bounds and cutting planes for the solution by branch- and-cut methods.
Mathematics Subject Classification ID: 90B30
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C11
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 474774
zbMATH Keywords: production scheduling
zbMATH Keywords: integer linear program
zbMATH Keywords: heuristic
zbMATH Keywords: lower bounds
zbMATH Keywords: cutting planes
zbMATH Keywords: branch-and-cut
reviewed by: I. N. Lushchakova
MaRDI profile type: Publication
cites work: Efficient reformulation for 0-1 programs -- methods and computational results
cites work: Solving Large-Scale Zero-One Linear Programming Problems
cites work: Bottleneck extrema
cites work: The Fixed Job Schedule Problem with Working-Time Constraints
cites work: On the Greedy Heuristic for Continuous Covering and Packing Problems
cites work: Q3686494
cites work: Technical Note—Stronger Inequalities for 0-1 Integer Programming: Computational Refinements
cites work: Solving capacitated clustering problems
cites work: Q4040221
cites work: Easily Computable Facets of the Knapsack Polytope
description: scientific article; zbMATH DE number 474774