We formulate a general sequencing problem that includes two classes of jobs with setup times, setup costs, holding costs, and deadlines. The formulation is unique in its explicit recognition of the opportunities to exploit productive capacity increases due to batching. An algorithm based on tabu search is then used as a solution method. Computational results are presented that suggest that the algorithm is effective.
BakerK. R. (1974), Introduction to Sequencing and Scheduling, John Wiley and Sons, New York.
2.
BakerK. R., and ScudderG. D. (1990), “Sequencing with Earliness and Tardiness Penalties: A Review,”Opns. Res., 38, 22–36.
3.
BrunoJ., and DowneyP. (1978), “Complexity of Task Sequencing with Deadlines, Set‐up Times and Changeover Costs,”SIAM J. Comput., 7, 393–404.
4.
ConwayR. W.MaxwellW. L., and MillerL. W. (1967), Theory of Scheduling, Addison‐Wesley, Reading, Massachusetts.
5.
DriscollW. C. (1975), “Scheduling Production on One Machine with Changeover Times,”invited paper given at the Fall 1975 ORSA‐TIMS Joint National Meeting.
6.
ErschlerJ.FontanG.MerceC., and RoubellatF. (1983), “A New Dominance Concept in Scheduling n Jobs on a Single Machine with Ready Times and Due Dates,”Opns. Res., 31, 114–127.
7.
FrenchS. (1982), Sequencing and Scheduling: An Introduction to the Mathematics of the Job‐Shop, John Wiley and Sons, New York.
8.
GoldrattE. M., and FoxR. E. (1986), The Race, North River Press, Croton‐on‐Hudson, New York.
9.
GloverF. (1989a), “Artificial Intelligence in Heuristic Solution Methods,” In Proc. 1989 Annual Meeting of Dec. Sci. Inst., 16–23.
GloverF. (1989c), “Candidate List Strategies and Tabu Search,” Technical Report, Center for Applied Artificial Intelligence, Box 419, University of Colorado, Boulder, CO, 80309, July, 1989.
12.
GloverF. (1990), “Tabu Search–Part II,”ORSA Journal on Computing, 2, 4–32.
13.
HallW. R. (1983), Zero Inventories, Dow Jones‐Irwin, Homewood, IL.
14.
JohnsonD. S.AragonC. R.McGeochL. A., and SchevonC. (1989), “Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning,”Ops. Res., 37‐6. 865–892.
15.
KanetJ. J. (1988), “MRP 96: Time to Rethink Manufacturing Logistics,”Prod, and Inv. Mgt. Jour., 29, 57–61.
16.
KanetJ. J., and ChristyD. P. (1984), “Manufacturing Systems with Forbidden Early Order Departure,”Int. J. Prod. Res., 22, 41–50.
17.
KarmarkarU. S. (1987), “Lot Sizes, Lead Times and In‐Process Inventories,”Mgmt. Sci., 33, 409–423.
18.
LagunaM.BarnesJ. W., and GloverF. (1990), “Scheduling Jobs with Linear Delay Penalties and Sequence Dependant Setup Costs and Times Using Tabu Search,” Research Report, Department of Mechanical Engineering, The University of Texas‐Austin, 1990.
19.
MondenY. (1983), Toyota Production System: Practical Approach to Management, Industrial Engineering and Management Press, Norcross, GA.
20.
MonmaC. L., and PottsC. N. (1989), “On the Complexity of Scheduling With Batch Setup Times,”Ops. Res., 37, 798–804.
21.
RyanJ. (1989), “Final Report of the Mathematics Clinic: Heuristics for Combinatorial Optimization,”Mathematics Department, University of Colorado, Boulder, CO.
22.
Skorin‐KapovJ. (1990), “Tabu Search Applied to the Quadratic Assignment Problem,”ORSA Journal on Computing, 2, 33–45.
23.
SpearmanM. L.WoodruffD. L., and HoppW. J. (1990), “CONWIP: A Pull Alternative to Kanban,”International Journal of Production Research, 28, 879–894.
24.
TrigeiroW. W.ThomasL. J., and McclainJ. O. (1989), “Capacitated Lot Sizing with Setup Times,”Mgmt. Sci., 35, 353–356.
