An extension of the General Job Shop Scheduling Problem

The increasing complexity of real-world production systems leads companies to face the tough problem of planning the flow of events and activities on a daily basis. Challenging decisions have to be made regarding the allocation of a broad variety of resources and corresponding task processing sequences. Current market trends demand efficient, effective, and accurate scheduling which is complex in all but the simplest production environment, therefore efficient schedules have an enormous effect on the long-term success of an enterprise. Thus, for many decades one of the most ambitious goals of researchers in programming theory has been to ensure reliable decision support for human planners. Although several classical scheduling problems are well studied, the integration of real-world constraints and objectives shows a lack of theoretical understanding. In order to provide an alternative approach in this direction, a new work environment is investigated with regard to the minimization of the strong assumptions imposed on the nature of the machines and the operations to be performed and the addition of parameters that reflect real-life conditions. The term scheduling refers to a vast class of problems, very different from each other in complexity and structure. In particular, the job shop scheduling problem is a well-known combinatorial optimization problem in computer science and operations research, and it is ubiquitous in many industries such as manufacturing and transportation. However, unlike what happens for other areas of combinatorial optimization, for the most difficult scheduling problems it is not possible to indicate a single clearly preferable approach for their solution, but from time to time it may be more appropriate to use heuristics, enumeration algorithms, approximate algorithms. A possible way to define scheduling problems is to refer to the application environment in which these problems arose, and so scheduling problems can be said to be all those decision-making problems in which the time factor is crucial, seen as a (scarce) resource to be optimally allocated to certain activities. Production scheduling is part of the shop management decision system and it is defined as the determination of the order in which a set of jobs is to be processed through a set of machines. In real-life situations, jobs may be interpreted as aircraft queuing up to land, or as a patient waiting to be treated by a consultant surgeon, or as bank customers at a row of tellers’ windows. Correspondingly, one would identify machines with an airport, or with surgical facilities, or with bank tellers, respectively. This thesis focuses the attention on the representation of the production plant as a system that, at time tn, is in a certain state, from which it is possible to move through the constraints on the machines and the operations in order to calculate all the possible states at time tn+k, k ∈ N. This approach transforms the job shop scheduling problem into the search for the best path in a tree, T , that is dynamically created whenever decisions are made about future states. Therefore, each node of T represents a state of the system. As one can imagine, the number of child nodes explodes quite quickly, and thus the complete enumeration of all the possibilities to identify feasible schedules and the optimal one is not practical. Therefore, the need to rely on heuristics arises.