Polish Journal of Management Studies
 ISSN 2081-7452
Go to content

Main menu:


Abstracts > Vol 1


Hoeck M.*


This paper provides an application oriented analysis of a multiple constraint scheduling procedure called SLSP, which is designed to batch and sequence production orders simultaneously.  The Simultaneous Lotsizing and Scheduling Procedure (SLSP) is easy to implement in a Shop Floor Control System and leads to good results for finite loading problems. Dependent on the data available and the goal of production control SLSP can be used to  minimize production costs or any other objective function, like minimizing the mean flow time or tardiness of the jobs. The approach is primarily based on a combination of regular dispatching rules and local search heuristics, such as Simulated Annealing,  Threshold Accepting or Tabu Search. Additionally the procedure contains a special routine to calculate lot sizes using the Aspired Machine Time (AMT) as a control parameter. (JEL: E23,M11,P42)

Key Words: scheduling, batching, flexible routing, local search algorithms


Manufactures of low to medium volume parts frequently face difficulties handling changes in the order stock or machine breakdowns, since most commercial Manufacturing Planning and Control Systems (MPC-Systems) are lacking of efficient scheduling procedures.  The successive expansion of standard MPC-Software - starting with a central MRP-Unit, which was extended by additional features like Capacity Requirements and Master Production Planning - is one reason why process control is often not supported as necessary.  Another reason is that production scheduling has become more complex.  

Due to technological improvements in the machine tools the versatility of workcenters, especially the ability to produce a wide variety of part types using different cutting tools,  has increased. This machine versatility provides scope for several routes of a part type and can be utilized to alleviate bottlenecks. Furthermore additional constraints, e.g. the limited number of tool slots at each machining center, have to be considered  while scheduling production orders in a modern Job Shop environment.

In order to reduce the complexity of production scheduling a number of advanced MPC-Systems include decentralized Shop Floor Control Systems (Bauer et al. 1991), such as a Leitstand. A Leitstand is an interactive Information- and Scheduling-System, implemented  on a Workstation or a PC, to monitor and control the material flow of one or more workcenters. Order data can either be inserted directly into the Leitstand or loaded automatically from the central MPC-System. It is also used to maintain data regarding  operations, precedence constraints as well as the NC program library and production environment data including machine, shift and calendar information. The Scheduling System of a Leitstand usually provides hooks for all necessary dispatching rules and  sometimes even more sophisticated optimization routines that can be used to improve an existing schedule.

... more in full version


In this paper we introduced an application oriented approach of lot sizing and scheduling in a Job Shop environment. The aim of SLSP is not to create a minute-based timetable, but to  find a good allocation and sequence of the production orders subject to organizational and technological constraints. At a first stage a rough cut order release is performed to control the workload, work-in-process inventory and tardiness in the Job Shop.  Afterwards the urgen production orders are batched and scheduled using a systems approach that can be adapted to the priorities of the scheduler.

The key control parameter of SLSP is the Aspired Machine Time (AMT), which defines the adequate processing time of a machining center before it can be set up to a new job. The adequate processing time of a machining center depends on the overall goal  of production control and the current state of the workcenter, whether the machine is a bottleneck or nonbottleneck resource. As a result of the routing flexibility in a modern Job Shop bottlenecks are rarely known in advance or may shift within the planning  period. Therefore one should apply a simulation run using a regular dispatching rule to determine the AMTs of the workcenters, which takes only a few seconds on a regular PC.

To improve a given schedule the described scheduling procedure can be applied, which combines regular dispatching rules and local search.SLSP can easily be adapted to additional constraints, such as local buffer and workforce capacities. In general, scheduling  constraints diminish the set of alternatively dispatchable operations, thus increasing the speed of local search. On the other hand, additional availability checks have to be performed, which prolong the computational time of the dispatching rules.  Therefore  only hard constraints that determine the feasibility of the schedules should be considered in SLSP.


[1]   Aarts E., Van Laarhoven P., Lenstra J. and Ulder N., A Computational Study of Local Search Algorithms for Job Shop Schedulin, ORSA Journal of Computing, Vol. 6, No. 2, 1994.
[2]   Adams J., Balas E. and Zawack, D., The Shifting Bottleneck Procedure for Job Shop Scheduling, Management Science, Vol. 34, No. 3, 1988.
[3]   Balas E. and Vazacopoulos  A., A Guided Local Search for Job Shop Scheduling, Working Paper POM WP-01, Fairleigh Dickinson University 1995.
[4]   Bauer A., Bowden R., Browne J., Duggan J. and Lyons G., Shop Floor Control Systems, London et al. 1991.
[5]   Calabrese J. M. and Hausmann W. H., Simultaneous Determination of Lot Sizes and Routing Mix in a Job Shop, Management Science, Vol. 37, No. 8, 1991.
[6]   Cerny V., Thermodynamical Approach to the Traveling Salesman Problem, Journal of Optimization Theory and Applications, Vol. 45, No. 1, 1985.
[7]   De Werra D. and Hertz A., Tabu Search Techniques, OR Spektrum, Vol. 11., No. 1, 1998.
[8]   Dueck G., New Optimization Heuristics, Journal of Computational Physics, Vol. 104, 1993.
[9]   Glover F.,  Future paths for integer programming and links to artificial intelligence, Computers and Operations Research, Vol. 13, 1986.
[10]   Fleischmann B., The Discrete Lot-Sizing and Scheduling Problem, European Journal of Operational Research, Vol. 44, No. 3, 1990, Fry T., Cox J., Blackstone J. and Hoffmann T., An Analysis and Discussion of the Optimized Production Technology Software  and Its Use, Production and Operations Management, Vol.1, No. 2, 1992.
[11]   Karmarkar U. S., Lot Sizes, Lead Times and In-Process Inventories, Management Science, Vol. 33, No. 3.
[12]   Kirkpatrik S., Gelatt C. and Vecchi M., Optimization by Simulated Annealing, Science, Vol. 220, No. 4598, 1983.
[13]   Matsuo H., Suh C. and Sullivan R.,  Controlled Search Simulated Annealing Algorithm for the General Jobshop Scheduling Problem, Working Paper 3-4-88, Department of Management, Graduate School of Business, University of Texas, Austin 1988.
[14]   Pinedo M., Commentary on An Exposition of Multiple Constraint Scheduling as Implemented in the Goal System, Production and Operations Management, Vol. 6, No. 1, 1997.
[15]   Simons J. V. and Simpson W. P. , An Exposition of Multiple Constraint Scheduling as Implemented in the Goal System, Production and Operations Management, Vol. 6, No. 1., 1997.
[16]   Solomon M., Deterministic Lotsizing Models for Production Planning, Berlin et al. 1991.
[17]   Sugimor Y., Kusunoki K., Cho F. and Uchikawa, S., Toyota Production System and Kanban System Materialization of Just-In-Time and Respect-For-Human System, International Journal of Production Research, Vol. 15, No. 6, 1977.
[18]   Van Laarhoven P., Aarts, E. And Lenstra, J., Job Shop Scheduling by Simulated Annealing, Operations Research, Vol. 40, No. 1.
[19]   Van Laarhoven P.and Aarts E., Simulated Annealing, Dordrecht 1987.
[20]   Veassens R., Aarts E. and Lenstra J., Job Shop Scheduling by Local Search, Memorandum COSOR 94-5 (revised version), Department of Mathematics and Computing Science, Eindhoven University of Technology, Eindhoven 1994.



Artykul przedstawia praktyczna analize zastosowania tzw. procedury planowania SLPS z wieloma ograniczeniami, ktora zostala zaprojektowania na potrzeby realizacji zamowien produkcji  seryjnej oraz sekwencyjnej. W systemie sterowania produkcja (ang. Shop Floor Control) mozna bardzo latwo zaimplementowac procedure rownoleglego ustalania wielkosci zamowienia i planowania (ang. Simultaneous Lotsizing and Scheduling Procedure (SLSP)),  co prowadzi do dobrych rezultatow w przypadku problemow z ocena zdolnosci produkcyjnych (ang. finite loading problems). W zaleznosci od dostepnych danych oraz celu kontroli produkcji, SLSP moze byc wykorzystana do zminimalizowania kosztow produkcji lub  innych rzeczywistych funkcji, jak np. zminimalizowanie sredniego czasu przeplywu lub opoznien zadan. Zaproponowane w artykule podejscie poczatkowo opiera sie na zasadach regularnych regul priorytetu i heurystykach lokalnego wyszukiwania, takich jak symulowane  wyzarzanie, akceptacja progowa, czy przeszukiwanie tabu (ang. Tabu search). Ponadto SLSP zawiera specjalna procedure obliczania wielkosci zamowienia z wykorzystaniem aspiracyjnej maszyny czasowej (Aspired Machine Time - AMT) w roli parametru kontrolnego.

Back to content | Back to main menu