Cyclic scheduling heuristics for a re-entrant job shop manufacturing environment

Two efficient cyclic scheduling heuristics for re-entrant job shop environments were developed. Each heuristic generated an efficient and feasible cyclic production schedule for a job shop in which a single product was produced repetitively on a set of machines was to determine an efficient and feasible cyclic schedule which simultaneously minimized flow time and cycle time. The first heuristic considered a repetitive production re-entrant job shop with a predetermined sequence of operations on a single product with known processing times, set-up and material handling times. The second heuristic was a specialization of the first heuristic where the set-up for an operation could commence even while the preceding operation was in progress. These heuristics have been extensively tested and computational results are provided. Also, extensive analysis of worst-case and trade-offs between cycle time and flow time are provided. The results indicate that the proposed heuristics are robust and yield efficient and superior cyclic schedules with modest computational effort.     

考虑急件到达的单机鲁棒调度方法

实际生产过程中经常会有急件到达。由于急件的优先级最高,其到达容易扰乱初始调度,使实际调度性能恶化,影响调度目标的实现。针对以总拖期为目标且带有释放时间的单机调度问题,研究了在有急件到达情况下的鲁棒调度方法,以降低急件对实际调度性能的影响。鉴于该调度问题是NP hard问题,根据工件释放时间和交货期的关系构造“金字塔”结构,获得该调度问题的占优性质。根据这些占优性质和急件到达特点,研究急件到达情景下的占优规则,据此求解急件到达情景下的占优调度集合,作为鲁棒调度的备选调度方案集合。提出了应对急件到达的鲁棒调度算法。给出仿真算例验证了算法的有效性,算例表明本文给出的鲁棒调度方法能有效避免急件到达造成实际调度性能的恶化。      

Finite capacity scheduling using a predetermined placement sequence

This paper presents a new heuristic for the finite capacity scheduling of factories. It treats the task of scheduling a factory the same as scheduling a large project that has many delivery points. The job placement sequence on machines is used as a link between infinite capacity schedules and finite capacity schedules. An ideal placement sequence is proposed from the infinite capacity backward schedule and this is embedded into the project network for finite capacity scheduling. This allows a finite capacity algorithm whose boundary condition is the most tightly packed schedule possible, and is also ideal from a cash flow perspective. The paper proposes a preference list of machines as an integral part of the scheduling process and shows how to switch between machines using preferences. It also shows how to integrate infinite and finite capacity schedules within the same algorithm by using a parameter called the constraint horizon. The heuristic is explained using input-output matrices and by working through an example of a project network. The example includes a discussion of circuits and a detailed explanation of how to implement the heuristic in a computer program.     

A new Nawaz–Enscore–Ham-based heuristic for permutation flow-shop problems with bicriteria of makespan and machine idle time

A new heuristic based on the Nawaz–Enscore–Ham algorithm is proposed in this article for solving a permutation flow-shop scheduling problem. A new priority rule is proposed by accounting for the average, mean absolute deviation, skewness and kurtosis, in order to fully describe the distribution style of processing times. A new tie-breaking rule is also introduced for achieving effective job insertion with the objective of minimizing both makespan and machine idle time. Statistical tests illustrate better solution quality of the proposed algorithm compared to existing benchmark heuristics.     

Priority Assignment Procedures in Multi-Level Assembly Job Shops

This paper deals with the design of priority rules for job shops that process multi-level assembly jobs. Specifically, it explores the means by which the structural complexity of jobs can be incorporated explicitly into priority rules to reduce job lead times. The job lead time is viewed as consisting of two components: flow time and job staging delays. The primary focus of the paper is on the development of a class of priority rules that is aimed at reducing the staging delay. The class of priority rules that is developed is then used in combination with rules that are effective for the flow time component. The combined rule results in the improvement of the lead time performance. The paper also includes experimental results on sets of jobs of varying degrees of complexity. These results provide a comparative perspective on the performance of priority rules that have been examined in the earlier research literature as well as the rules specifically developed in this paper.     

Learning dispatching rules using random forest in flexible job shop scheduling problems

In this paper, we address the flexible job-shop scheduling problem (FJSP) with release times for minimising the total weighted tardiness by learning dispatching rules from schedules. We propose a random-forest-based approach called Random Forest for Obtaining Rules for Scheduling (RANFORS) in order to extract dispatching rules from the best schedules. RANFORS consists of three phases: schedule generation, rule learning with data transformation, and rule improvement with discretisation. In the schedule generation phase, we present three solution approaches that are widely used to solve FJSPs. Based on the best schedules among them, the rule learning with data transformation phase converts them into training data with constructed attributes and generates a dispatching rule with inductive learning. Finally, the rule improvement with discretisation improves dispatching rules with a genetic algorithm by discretising continuous attributes and changing parameters for random forest with the aim of minimising the average total weighted tardiness. We conducted experiments to verify the performance of the proposed approach and the results showed that it outperforms the existing dispatching rules. Moreover, compared with the other decision-tree-based algorithms, the proposed algorithm is effective in terms of extracting scheduling insights from a set of rules.     

Cyclic Assembly Schedules

Cyclic assembly schedules are schedules which follow a repeating production pattern. Each component is produced at times that are integer multiples of the base planning period of the finished product. These schedules have the managerial advantages of ease of control and planning, since future production follows a familiar, repeating pattern. Establishing and maintaining such a schedule requires a system to protect the schedule when bottlenecks occur. This paper discusses some of these issues and describes a simple method for calculating the optimal parameters of a cyclic schedule in a multistage assembly operation when production intervals are power-of-two multiples of a base period specified by management. The cycles are based on an Economic Order Quantity analysis, which is applicable if demand for the end items is fairly steady as in the case of a facility that supplies components to an assembly line.     

Scheduling with alternatives: a link between process planning and scheduling

The objective of this research is to develop and evaluate effective, computationally efficient procedures for scheduling jobs in a large-scale manufacturing system involving, for example, over 1000 jobs and over 100 machines. The main performance measure is maximum lateness; and a useful lower bound on maximum lateness is derived from a relaxed scheduling problem in which preemption of jobs is based on the latest finish time of each job at each machine. To construct a production schedule that minimizes maximum lateness, an iterative simulation-based scheduling algorithm operates as follows: (a) job queuing times observed at each machine in the previous simulation iteration are used to compute a refined estimate of the effective due date (slack) for each job at each machine; and (b) in the current simulation iteration, jobs are dispatched at each machine in order of increasing slack. Iterations of the scheduling algorithm terminate when the lower bound on maximum lateness is achieved or the iteration limit is reached. This scheduling algorithm is implemented in Virtual Factory, a Windows-based software package. The performance of Virtual Factory is demonstrated in a suite of randomly generated test problems as well as in a large furniture manufacturing facility. To further reduce maximum lateness, a second scheduling algorithm also incorporates a tabu search procedure that identifies process plans with alternative operations and routings for jobs. This enhancement yields improved schedules that minimize manufacturing costs while satisfying job due dates. An extensive experimental performance evaluation indicates that in a broad range of industrial settings, the second scheduling algorithm can rapidly identify optimal or nearly optimal schedules.     

Robust scheduling of a two-machine flow shop with uncertain processing times

This paper focuses on manufacturing environments where job processing times are uncertain. In these settings, scheduling decision makers are exposed to the risk that an optimal schedule with respect to a deterministic or stochastic model will perform poorly when evaluated relative to actual processing times. Since the quality of scheduling decisions is frequently judged as if processing times were known a priori, robust scheduling, i.e., determining a schedule whose performance (compared to the associated optimal schedule) is relatively insensitive to the potential realizations of job processing times, provides a reasonable mechanism for hedging against the prevailing processing time uncertainty. In this paper we focus on a two-machine flow shop environment in which the processing times of jobs are uncertain and the performance measure of interest is system makespan. We present a measure of schedule robustness that explicitly considers the risk of poor system performance over all potential realizations of job processing times. We discuss two alternative frameworks for structuring processing time uncertainty. For each case, we define the robust scheduling problem, establish problem complexity, discuss properties of robust schedules, and develop exact and heuristic solution approaches. Computational results indicate that robust schedules provide effective hedges against processing time uncertainty while maintaining excellent expected makespan performance     

A discrete time reactive scheduling model for new order insertion in job shop,make-to-order industries

This research presents a new reactive scheduling methodology for job shop, make-to-order industries. An integer linear programming formulation previously developed by the authors to schedule these types of industries is extended to address the problem of inserting new orders in a predetermined schedule, which is important in order-driven industries. A reactive scheduling algorithm is introduced to iteratively update the schedules. Numerical results on realistic examples of job shops of different sizes illustrate the effectiveness of the approach. In each case, different alternatives for inserting a set of new orders in an initial schedule are optimally generated, enabling the user to choose the most convenient one. Solutions are characterised by measures of scheduling efficiency as well as stability measures that assess the impact of rescheduling operations in a previously defined scheduling solution.     

A multiple-pass heuristic rule for job shop scheduling with due dates

This paper presents an efficient multiple-pass heuristic algorithm for job shop scheduling problems with due dates wherein the objective is to minimize total job tardiness. Algorithm operation is carried out in two phases. In phase 1 a dispatching rule is employed to generate an active or non-delay initial schedule. In phase 2, tasks selected from a predetermined set of promising target operations in the initial schedule are tested to ascertain whether by left-shifting their start times and rearranging some subset of the remaining operations one can reduce total tardiness. Performance evaluation is carried out over a range of shop sizes focusing, first of all, on the quality of the initial schedule produced through five commonly used dispatching rules and, secondly, the schedule improvement achieved with the multiple-pass heuristic. Results indicate that the proposed technique is capable of yielding notable reductions in total tardiness (over initial schedules) for practical size problems and would suggest that the approach presents an efficient scheduling option for this class of complex optimization problems.     

MULTI-PROJECT SCHEDULING WITH EXPLICIT LATENESS COSTS

We propose a heuristic procedure for planning and scheduling multiple projects subject to limited resource availabilities. We depart from previous research in that explicit lateness costs for each project are considered. Our procedure involves aggregate analysis using linear programming to determine target resource loading profiles for each project that optimize trade-offs of lateness costs among projects, followed by detailed multi-project scheduling consistent with the target profiles. Target profiles and detailed schedules are iteratively modified through N iterations, where N is the number of projects. The procedure can be used to jointly schedule previously committed and newly proposed projects, as well as to assign due dates to proposed projects. We compare the performance of our procedure to that of the traditional minimum slack heuristic, as well to a simple extension of the minimum slack rule that accounts for lateness costs. On a set of 60 multi-project test problems adapted from the Patterson set of single-project problems, results are very favorable for our proposed algorithm.     

An efficient technique to solve combined economic and emission dispatch problem using modified Ant colony optimization

Economic load dispatch is one of the vital purposes in electrical power system operation, management and planning. Economic dispatch problem is one of the most important problems in electric power system operation. In large scale system, the problem is more complex and difficult to find out optimal solution because it is nonlinear function and it contains number of local optimal. Combined economic emission dispatch (CEED) problem is to schedule the committed generating units outputs to meet the required load demand at minimum operating cost with minimum emission simultaneously. The main aim of economic load dispatch is to reduce the total production cost of the generating system and at the same time the necessary equality and inequality constraints should also be fulfilled. This leads to the development of CEED techniques. There are various techniques proposed by several researchers to solve CEED problem based on optimization techniques. But still some problems such as slower convergence and higher computational complexity exist in using the optimization techniques such as GA for solving CEED problem. This paper proposes an efficient and reliable technique for combined fuel cost economic optimization and emission dispatch using the Modified Ant Colony Optimization algorithm (MACO) to produce better optimal solution. The simulation results reveal the significant performance of the proposed MACO approach.     

A Compromise Programming to Task Assignment Problem in Software Development Project

The scheduling process that aims to assign tasks to members is a difficult job in project management. It plays a prerequisite role in determining the project’s quality and sometimes winning the bidding process. This study aims to propose an approach based on multi-objective combinatorial optimization to do this automatically. The generated schedule directs the project to be completed with the shortest critical path, at the minimum cost, while maintaining its quality. There are several real-world business constraints related to human resources, the similarity of the tasks added to the optimization model, and the literature’s traditional rules. To support the decision-maker to evaluate different decision strategies, we use compromise programming to transform multi-objective optimization (MOP) into a single-objective problem. We designed a genetic algorithm scheme to solve the transformed problem. The proposed method allows the incorporation of the model as a navigator for search agents in the optimal solution search process by transferring the objective function to the agents’ fitness function. The optimizer can effectively find compromise solutions even if the user may or may not assign a priority to particular objectives. These are achieved through a combination of non-preference and preference approaches. The experimental results show that the proposed method worked well on the tested dataset.     

Scheduling a no-wait flow shop containing unbounded batching machines

We study the problem of scheduling n jobs in a no-wait flow shop consisting of m batching machines. Each job has to be processed by all the machines. All jobs visit the machines in the same order. A job completed on an upstream machine should be immediately transferred to the downstream machine. Batching machines can process several jobs simultaneously in a batch so that all jobs of the same batch start and complete together. The processing time of a batch is equal to the maximum processing time of the jobs in this batch. We assume that the capacity of any batch is unbounded. The problem is to find an optimal batch schedule such that the maximum job completion time, that is the makespan, is minimized. For m = 2, we prove that there exists an optimal schedule with at most two batches and construct such a schedule in O(n log n) time. For m = 3, we prove that the number of batches can be limited to nine and give an example where all optimal schedules have seven batches. Furthermore, we prove that the best schedules with at most one, two and three batches are 3-, 2- and 3/2-approximate solutions, respectively. The first two bounds are tight for corresponding schedules. Finally, we suggest an assignment method that solves the problem with m machines and at most r batches in O(n^{m(r-2)+1+[m/r]}) time, if m and r are fixed. The method can be generalized to minimize an arbitrary maximum cost or total cost objective function.     

A hybrid genetic algorithm and tabu search for a multi-objective dynamic job shop scheduling problem

In most real manufacturing environments, schedules are usually inevitable with the presence of various unexpected disruptions. In this paper, a rescheduling method based on the hybrid genetic algorithm and tabu search is introduced to address the dynamic job shop scheduling problem with random job arrivals and machine breakdowns. Because the real-time events are difficult to express and take into account in the mathematical model, a simulator is proposed to tackle the complexity of the problem. A hybrid policy is selected to deal with the dynamic feature of the problem. Two objectives, which are the schedule efficiency and the schedule stability, are considered simultaneously to improve the robustness and the performance of the schedule system. Numerical experiments have been designed to test and evaluate the performance of the proposed method. This proposed method has been compared with some common dispatching rules and meta-heuristic algorithms that have been widely used in the literature. The experimental results illustrate that the proposed method is very effective in various shop-floor conditions.     

Lot streaming with attached setups in three-machine flow shops

Lot streaming is the process of splitting a job or lot to allow overlapping between successive operations in a multistage production system. This use of transfer lots usually results in a significantly shorter makespan for the schedule. We study the structural properties of schedules which minimize the makespan for a single job with attached setup times in a flow shop. The structure of the optimal schedules is more complex than in the case with no setups or detached setups, as it may follow a much larger variety of patterns. Using the structural insights obtained, however, it is possible to find the optimal solution with s sublots in O(s) time for the three-machine case.     

Cyclic job scheduling in paced assembly lines with cross-trained workers

Paced or synchronous assembly lines allow concurrent manufacturing of a mix of products by repetitive production of a minimal product set (MPS). We refer to the associated production schedules as cyclic. We consider a paced assembly line where every job (or order) visits all m assembly stations in the same sequence and spends the same amount of time (known as the production cycle) at each station, by using the appropriate number of workers. Hence, associated with each job is an m-tuple of workforce requirements. Our objective is to find a cyclic schedule of jobs such that the total required workforce size is minimized. Assuming that each worker is cross-trained to work at a number of stations, we show that the problem is strongly NP-complete. In light of this result, we develop lower bounds, heuristic algorithms and an optimal branch-and-bound procedure. Our computational experiments show that our algorithms are computationally efficient and exhibit near-optimal performance. We also compare the savings in workforce size among systems with various levels of cross training.     

Short-term scheduling of an open-pit mine with multiple objectives

This article presents a novel algorithm for the generation of multiple short-term production schedules for an open-pit mine, in which several objectives, of varying priority, characterize the quality of each solution. A short-term schedule selects regions of a mine site, known as ‘blocks’, to be extracted in each week of a planning horizon (typically spanning 13 weeks). Existing tools for constructing these schedules use greedy heuristics, with little optimization. To construct a single schedule in which infrastructure is sufficiently utilized, with production grades consistently close to a desired target, a planner must often run these heuristics many times, adjusting parameters after each iteration. A planner's intuition and experience can evaluate the relative quality and mineability of different schedules in a way that is difficult to automate. Of interest to a short-term planner is the generation of multiple schedules, extracting available ore and waste in varying sequences, which can then be manually compared. This article presents a tool in which multiple, diverse, short-term schedules are constructed, meeting a range of common objectives without the need for iterative parameter adjustment.     

Production sequencing problem with re-entrant work flows and sequence dependent setup times

This paper addresses a shop scheduling problem where a set of n jobs needs to be scheduled on two machines for the side frame press shop in a truck manufacturing company. A most unusual aspect of the problem is that the setup times required for a job in the first machine depend not on the immediately preceding job but on the job which is two steps prior to it. Redefining the job elements, the problem is formulated into a general two machine flow shop problem which can be solved by dynamic programming with the objective of the minimum makespan. An optimal schedule is found utilizing the sequence dominance conditions and the decisiondelay scheme. Since the computational requirements of dynamic programming are impracticably demanding for large-sized problems, a genetic algorithm is developed and its performance is examined through a comparative study.