The job shop scheduling problem

Available under Creative Commons-ShareAlike 4.0 International License.

The two key problems in production scheduling are „priorities“ and „capacity“. Wight (1974) described scheduling as „establishing the timing for performing a task“ and observes that, in manufacturing firms, there are multiple types of scheduling, including the detailed scheduling of a shop order that shows when each operation must start and be completed 1. Baker (1974) defined scheduling as „a plan than usually tells us when things are supposed to happen“ 2. Cox et al. (1992) defined detailed scheduling as „the actual assignment of starting and/or completion dates to operations or groups of operations to show when these must be done if the manufacturing order is to be completed on time“3. Pinedo (1995) listed a number of important surveys on production scheduling4. For Hopp and Spearman (1996) „scheduling is the allocation of shared resources over time to competing activities“ 5. Makowitz and Wein (2001) classified production scheduling problems based on attributes: the presence of setups, the presence of due dates, the type of products.

Practical scheduling problems, although more highly constrained, are high difficult to solve due to the number and variety of jobs, tasks and potentially conflicting goals. Recently, a lot of Advanced Production Scheduling tools arose into the market (e.g., Aspen PlantTM Scheduler family, Asprova, R2T – Resourse To Time, DS APS – DemandSolutions APS, DMS – Dynafact Manufacturing System, i68Group, ICRON-APS, JobPack, iFRP, Infor SCM, SchedulePro, Optiflow-Le, Production One APS, MQM – Machine Queue Management, MOM4, JDA software, Rob-ex, Schedlyzer, OMP Plus, MLS and MLP, Oracle Advanced Scheduling, Ortec Schedule, ORTEMS Productionscheduler, Outperform, AIMMS, Planet Together, Preactor, Quintiq, FactoryTalk Scheduler, SAP APO-PP/DS, and others). Each of these automatically reports graphs. Their goal is to drive the scheduling for assigned manufacturing processes. They implement rules and optimise an isolated sub-problem but none of the them will optimise a multi stage resource assignment and sequencing problem.

In a Job Shop (i.e., JS) problem a classic and most general factory environment, different tasks or operations must be performed to complete a job 6; moreover, priorities and capacity problems are faced for different jobs, multiple tasks and different routes. In this contest, each job has its own individual flow pattern through assigned machines, each machine can process only one operation at a time and each operation can be processed by only one machine at a time. The purpose of the procedure is to obtain a schedule which aims to complete all jobs and, at the same time, to minimize (or maximize) the objective function. Mathematically, the JS Scheduling Problem (i.e., JSSP) can be characterized as a combinatorial optimization problem. It has been generally shown to be NP-hard7 - belonging to the most intractable problems considered 8, 9, 10. This means that the computation effort may grow too fast and there are not universal methods making it possible to solve all the cases effectively. Just to understand what the technical term means, consider the single-machine sequencing problem with three jobs. How many ways of sequencing three jobs do exist? Only one of the three jobs could be in the first position, which leaves two candidates for the second position and only one for the last position. Therefore the no. of permutations is 3!. Thus, if we want to optimize, we need to consider six alternatives. This means that as the no. of jobs to be sequenced becomes larger (i.e., n>80), the no. of possible sequences become quite ominous and an exponential function dominates the amount of time required to find the optimal solution11. Scheduling, however, performs the definition of the optimal sequence of n jobs in m machines. If a set of n jobs is to be scheduled on m machines, there are (n!)^m possible ways to schedule the job.

It has to undergo a discrete number of operations (i.e., tasks) on different resources (i.e., machines). Each product has a fixed route defined in the planning phase and following processing requirements (i.e., precedence constraints). Other constraints, e.g. zoning which binds the assignment of task to fixed resource, are also taken into consideration. Each machine can process only one operation at a time with no interruptions (pre-emption). The schedule we must derive aims to complete all jobs with minimization (maximization) of an objective function on the given production plant.

Let:

JSSP, marked as Πj, consists in a finite set J of n jobs . Each J_{i is} characterized by a manufacturing cycle regarded as a finite set M of m machines with an uninterrupted processing time .  , is processed on a fixed machine and requires a chain of tasks , scheduled under precedence constraints. is the task of job which has to be processed on machine for an uninterrupted processing time period τik and no operations may pre-empted.

To accommodate extreme variability in different parts of a job shop, schedulers separate workloads in each work-centres rather than aggregating them12. Of more than 100 different rules proposed by researchers and applied by practitioners exist, some have become common in Operations Management systems: First come- First served, Shortest Processing Time, Earliest Due Date, Slack Time Remaining, Slack Time Remaining For each Operation, Critical Ratio, Operation Due Date, etc.13. Besides these, Makespan is often the performance feature in the study of resource allocation14. Makespan represents the time elapsed from the start of the first task to the end of the last task in schedule. The minimisation of makespan arranges tasks in order to level the differences between the completion time of each work phase. It tries to smooth picks in work-centre occupancy to obtain batching in load assignment per time. Although direct time constraints, such as minimization of processing time or earliest due date, are sufficient to optimize industrial scheduling problems, for the reasons as above the minimization of the makespan is preferable for general/global optimization performances because it enhances the overall efficiency in shop floor and reduces manufacturing lead time variability15.

Thus, in JSSP optimization variant of , the objective of a scheduling problem is typically to assign the tasks to time intervals in order to minimise the makespan and referred to as:

 

where t represent time (i.e. iteration steps)

 

and represents the starting time of k-th operation of i-th job. sik is the time value that we would like to determinate in order to establish the suited schedule activities order.