A comparative analysis of due date based job sequencing rules in a flow shop with multiple processors

The literature on job scheduling recognizes the importance of due date performance criteria such as mean tardiness and maximum tardiness. A number of studies test a large number of sequencing rules for these criteria in job shop and flow shop settings. The object of this present research is to examine the performance of some well-known priority rules in a flow shop with multiple processors. This study investigates the performance of ten priority rules in terms of mean and maximum tardiness. It examines the effects of problem characteristics, such as number of jobs, number of machines stages and number of parallel processors at each stage, and the performance of priority rules using regression analysis. The findings of the study suggest that the primary determinants of tardiness-based criteria are problem characteristics. In addition, both the regression analysis and the analysis of variance provide strong evidence of the strategy-effect. Finally, a detailed performance review of examined priority rules for various problem characteristics is presented.     

Dynamic selection of dispatching rules for job shop scheduling

Although the academic contribution to job shop scheduling is abundant, its impact on practice has been minimal. The most preferred approach to job shop scheduling in the industry is dispatching rules. A major criticism against dispatching rules is that there is no single universal rule. The effective choice of dispatching rules depends on the scheduling criterion and existing job shop conditions. In this paper, the authors have proposed a scheduling method based on the analytic hierarchy process, that dynamically selects the most appropriate dispatching rule from several candidate rules. The selection is based on the existing job shop conditions. This method is applied to two formal job shop problems, and the results for single dispatching rules are inferior to the method proposed in this paper.     

A simulated annealing algorithm for job shop scheduling

In this paper, the job shop scheduling problem is considered with the objective of minimization of makespan time. We first reviewed the literature on job shop scheduling using meta-heuristics. Then a simulated annealing algorithm is presented for scheduling in a job shop. To create neighbourhoods, three perturbation schemes, viz. pairwise exchange, insertion, and random insertion are used, and the effect of them on the final schedule is also compared. The proposed simulated annealing algorithm is compared with existing genetic algorithms and the comparative results are presented. For comparative evaluation, a wide variety of data sets are used. The proposed algorithm is found to perform well for scheduling in the job shop.     

Multi-objective permutation flow shop scheduling problem: Literature review,classification and current trends

The flow shop scheduling problem is finding a sequence given n jobs with same order at m machines according to certain performance measure(s). The job can be processed on at most one machine; meanwhile one machine can process at most one job. The most common objective for this problem is makespan. However, many real-world scheduling problems are multi-objective by nature. Over the years there have been several approaches used to deal with the multi-objective flow shop scheduling problems (MOFSP). Hence, in this study, we provide a brief literature review of the contributions to MOFSP and identify areas of opportunity for future research.     

Evaluation of scheduling strategies for a dynamic job shop in a tool-shared,flexible manufacturing environment

A two-phase approach is used to examine the impact of job scheduling rules and tool selection policies for a dynamic job shop system in a tool-shared, flexible manufacturing environment. The first phase develops a generalized simulation model and analyses 'simple' job scheduling rules and tool selection policies under various operating scenarios. The results from this investigation are then used to develop and analyse various bi-criteria rules in the second phase of this study. The results show that the scheduling rules have the most significant impact on system performance, particularly at high shop load levels. Tool selection policies affect some of the performance measures, most notably, proportion of tardy jobs, to a lesser degree. Higher machine utilizations can be obtained at higher tool duplication levels but at the expense of increased tooling costs and lower tool utilization. The results also show that using different processing time distributions may have a significant impact on shop performance.     

The permutation flow shop problem with just in time production considerations

This research presents a variation to the permutation flow shop problem where Just In Time (JIT) production requirements are taken into account. The model developed in this research employs dual objectives. In addition to the traditional objective of minimizing the production makespan, minimization of Miltenburg's material usage rate is also incorporated. In this model, multiple units of any product are permitted in the production sequence. However, the minimization of material usage rates attempts to prevent batch scheduling of products and allows unit flow of products as required in demand flow manufacturing. A solution method is proposed for determining an optimal production sequence via an efficient frontier approach and Simulated Annealing (SA). Test problems and specific performance criteria are used to assess the solutions generated by the proposed method. Experimental results presented in this paper show that the use of the efficient frontier and SA provide solutions that approach the optimal solution for the performance measures used in this research.     

Minimizing tardiness on a single processor with sequence-dependent setup times: a simulated annealing approach

In today's fast-paced Just-In-Time and mass customization manufacturing in a sequence-dependent setup environment, the challenge of making production schedules to meet due-date requirements is becoming a more complex problem. Unfortunately, much of the research on operations scheduling problems has either ignored setup times or assumed that setup times on each machine are independent of the job sequence. This paper considers the problem of minimizing tardiness, a common measure of due-date performance, in a sequence-dependent setup environment. Simulated annealing was used to solve the sequencing problem, and its performance was compared with random search. Our experimental results show that the algorithm can find a good solution fairly quickly, and thus can rework schedules frequently to react to variations in the schedule. The algorithm is invaluable for ‘on-line’ production scheduling and ‘last-minute’ changes to production schedule. The results of this research also suggest ways in which more complex and realistic job shop environments, such as multiple machines with a higher number of jobs in the sequence, and other scheduling objectives can be modeled. This research also investigates computational aspects of simulated annealing in solving complex scheduling problems.     

A Virtual Cellular Manufacturing Approach to Batch Production*

In this paper, Virtual Cellular Manufacturing (VCM), an alternative approach to implementing cellular manufacturing, is investigated. VCM combines the setup efficiency typically obtained by Group Technology (GT) cellular manufacturing (CM) systems with the routing flexibility of a job shop. Unlike traditional CM systems in which the shop is physically designed as a series of cells, family-based scheduling criteria are used to form logical cells within a shop using a process layout. The result is the formation of temporary, virtual cells as opposed to the more traditional, permanent, physical cells present in GT systems. Virtual cells allow the shop to be more responsive to changes in demand and workload patterns. Production using VCM is compared to production using traditional cellular and job shop approaches. Results indicate that VCM yields significantly better flow time and due date performance over a wide range of common operating conditions, as well as being more robust to demand variability.     

PCB assembly scheduling through kit concept

This paper presents the design and test of a new scheduling environment dedicated to the off-line scheduling of PCB assembly shops. The main idea introduced is the employment of the 'kit concept' as a scheduling tool, as opposed to the traditional batch scheduling. In the kit approach, the basic PCB aggregations are kits composed of different PCBs matching finished products requirements, instead of homogeneous batches of identical boards. By introducing the kit approach, PCB assembly schedule is intended to be focused more towards the assembly of final products than towards the internal PCB assembly shop constraints and requirements. A simulation model and data from a real assembly system are used to compare the kit approach with traditional batch processing. Experimental results show that the proposed kit approach jointly achieves remarkable improvements in the effectiveness and efficiency performances of the assembly system, as compared to the batch approach. However, it is determined also that these advantages can only be achieved if a sufficiently advanced scheduling system is used.     

Flexible reasoning using sensible agent-based systems: A case study in job flow scheduling

Planning and control systems for highly dynamic and uncertain manufacturing environments require adaptive flexibility and decision-making capabilities. Modern distributed manufacturing systems assess the utility of planning and executing solutions for both system goals (e.g. minimize manufacturing production time for all parts or minimize WIP) and local goals (e.g. expedite part A production schedule or maximize machine X utilization). Sensible Agents have the ability to alter their autonomy levels to choose among a set of decision models in order to handle the differences between local and system goals. In this paper, Sensible Agents are applied to a production planning and control problem in the context of job shop scheduling and decision model theory. Sensible Agents provide for trade-off reasoning mechanisms among system and local utilities that are flexible and responsive to an agent's abilities, situational context and position in the organizational structure of the system.     

A new three-machine shop scheduling: complexity and approximation algorithm

The paper investigates a new three-machine shop scheduling problem that arises from many production systems, such as the garment assembly line, etc. In such scenarios, each job consists of three operations, each of which has to be non-preemptively processed by one specific machine. In contrast with the classical three-machine shop scheduling, the processing order of the operations of each job is partially restricted. In particular, the first two operations are ordered and all the same for all jobs, while the third operation is not restricted. The objective is to minimize the makespan. We show the problem is NP-hard in the ordinary sense and present a polynomial time approximation algorithm with a worst case performance ratio of $\frac{3}{2}$ .     

A mathematical model for job shop scheduling with multiple process plan consideration per job

In this paper, a mixed integer programming model is formulated for scheduling a set of jobs through a shop when each job is supplied or provided with multiple process plans or process routings. Simultaneous selection of a process plan for each job and the sequencing of the jobs through the machines in the shop based on the set of selected process plans is addressed. The procedure developed seeks to integrate the selection of machines for each job and the sequencing of jobs on each machine based on the objective of minimizing production makespan. the application of the procedure is demonstrated with an example problem. The following conclusions were drawn as a result of the research: (1) the procedure developed produces optimal or near optimal solution; (2) the benefit from the developed approach is that it allows a shop to adaptively select process plans for jobs to optimize on production makespan. By combining solution quality with scheduling flexibility and efficiency, the productivity of a shop can be greatly enhanced.     

A comparative analysis of two different approaches to scheduling in flexible flow shops

This work is an investigation about the relative effectiveness of two approaches to scheduling in flexible flow shops: one approach advocating the possible use of different dispatching rules at different stages of the flow shop, and the other suggesting the use of the same dispatching rule at all the stages of the flow shop. In the latter approach, the dispatching rule contains the information related to both process time and duedate. Both approaches aim at the minimization of measures related to flowtime and tardiness of jobs. This paper essentially is an attempt at exploring the relative effectiveness of these two approaches to scheduling.     

An Experimental Comparison of Time-Based and Economic-Based Scheduling Methods to Maximize Net Present Value*

In the past, performance in dynamic-scheduling environments was primarily measured in terms of time or physical shop characteristics. Objectives such as mean tardiness, flow time, and work-in-process inventory were commonly used. Today, there is increasing interest in the use of more advanced economic performance measures. These measures have the more comprehensive objective of maximizing ownership wealth by economically scheduling jobs and tasks. This study presents a large-scale experiment testing time-based and economic-based scheduling methods in a dynamic job shop. These methods are evaluated on their ability to maximize net present value (NPV). The study considers the just-in-time (JIT) delivery environment. The job shop is hypothetical, but is based on models of real production situations. Results show that the use of very detailed economic information in a sophisticated manner generally improves economic performance. Where due dates are easy to achieve, however, time-based scheduling methods are at least as good as those based on economics. Also, where utilization is high and due dates tight, early cost information in release and dispatch is detrimental to schedule value.     

Asymptotically optimal policy for stochastic job shop scheduling problem to minimize makespan

This paper studies the large-scale stochastic job shop scheduling problem with general number of similar jobs, where the processing times of the same step are independently drawn from a known probability distribution, and the objective is to minimize the makespan. For the stochastic problem, we introduce the fluid relaxation of its deterministic counterpart, and define a fluid schedule for the fluid relaxation. By tracking the fluid schedule, a policy is proposed for the stochastic job shop scheduling problem. The expected value of the gap between the solution produced by the policy and the optimal solution is proved to be O(1), which indicates the policy is asymptotically optimal in expectation.     

Flow shop scheduling by transportation model

This paper describes the classical problem of scheduling n jobs on m machines in a flow shop. A schedule evaluation algorithm is presented, which for job-pairs, generates a schedule evaluation matrix. The matrix is the input data to a transportation problem, the solution of which gives near-optimal jobsequence and makespan. The performance of the algorithm is discussed.     

A multiobjective genetic algorithm for job shop scheduling

In this paper, a Multi Objective Genetic Algorithm (MOGA) is proposed to derive the optimal machine-wise priority dispatching rules ( pdrs ) to resolve the conflict among the contending jobs in the Giffler and Thompson (GT) procedure applied for job shop problems. The performance criterion considered is the weighed sum of the multiple objectives minimization of makespan, minimization of total idle time of machines and minimization of total tardiness. The weights assigned for combining the objectives into a scalar fitness function are not constant. They are specified randomly for each evaluation. This in turn leads to the multidirectional search in the proposed MOGA, which in turn mitigates the solution being entrapped in local minima. The applicability and usefulness of the proposed methodology for the scheduling of job shops is illustrated with 28 benchmark problems available in the open literature.     

A new prototype system for optimized job shop scheduling

Optimal scheduling of shopfloor activities in an environment of discrete part manufacturing is discussed. The scheduling problem is a well known NP complete one. The main part, the sequencing problem, has been tackled using two techniques: virtual resources identification and taboo search heuristics. The first approach allowed the authors to reduce the complexity of the sequencing from a job shop to a general flow shop problem. On the other hand, the search for an optimal solution, with respect to a fixed strategy, has been achieved via the taboo search. A synthesis of the results of a large number of tests is presented as well as the results of an application to a real case. The latter is shown in comparison with the output of the system being presently used in the examined factory.     

Minimizing the number of tardy jobs in two-machine settings with common due date

We consider two-machine scheduling problems with job selection. We analyze first the two-machine open shop problem and provide a best possible linear time algorithm. Then, a best possible linear time algorithm is derived for the job selection problem on two unrelated parallel machines. We also show that an exact approach can be derived for both problems with complexity \(O(p(n) \times \sqrt{2}^n)\), p being a polynomial function of n.     

Optimal job insertion in the no-wait job shop

The no-wait job shop (NWJS) considered here is a version of the job shop scheduling problem where, for any two operations of a job, a fixed time lag between their starting times is given. Also, sequence-dependent set-up times between consecutive operations on a machine can be present. The NWJS problem consists in finding a schedule that minimizes the makespan. We address here the so-called optimal job insertion problem (OJI) in the NWJS. While the OJI is NP-hard in the classical job shop, it was shown by Gröflin & Klinkert to be solvable in polynomial time in the NWJS. We present a highly efficient algorithm with running time $\mathcal {O}(n^{2}\cdot\max\{n,m\})$ for this problem. The algorithm is based on a compact formulation of the NWJS problem and a characterization of all feasible insertions as the stable sets (of prescribed cardinality) in a derived comparability graph. As an application of our algorithm, we propose a heuristic for the NWJS problem based on optimal job insertion and present numerical results that compare favorably with current benchmarks.