A Heuristic Algorithm for the Fabric Spreading and Cutting Problem in Apparel Factories

We study the fabric spreading and cutting problem in apparel factories. For the sake of saving the material costs, the cutting requirement should be met exactly without producing additional garment components. For reducing the production costs, the number of lays that corresponds to the frequency of using the cutting beds should be minimized. We propose an iterated greedy algorithm for solving the fabric spreading and cutting problem. This algorithm contains a constructive procedure and an improving loop. Firstly the constructive procedure creates a set of lays in sequence, and then the improving loop tries to pick each lay from the lay set and rearrange the remaining lays into a smaller lay set. The improving loop will run until it cannot obtain any smaller lay set or the time limit is due. The experiment results on 500 cases show that the proposed algorithm is effective and efficient.      

Improving schedule stability in single-machine rescheduling for new operation insertion

The problem studied here entails inserting a new operation into an existing predictive schedule (preschedule) on a (non-preemptive) single machine by rescheduling its operations, so that the resultant schedule is the most stable one among schedules with minimal maximum tardiness. Stability is measured by the sum of absolute deviations of post-rescheduling start times from the pre-rescheduling start times. In addition to several simple heuristics, this study investigates a hybrid branch-and-bound/local-search algorithm. A large set of instances that include cases with inserted idle times allows for tests of the performance of the heuristics for preschedules with varying degrees of robustness. The results show that algorithms can be developed that significantly improve the stability of schedules with no degradation in T_max. In addition, new insights emerge into the robustness characteristics of a preschedule. Specifically, the number of gaps in the schedule, equal distribution of total slack among these gaps, and the slack introduced beyond the amount enforced by release times all have effects on schedule robustness and stability.     

The economic lot scheduling problem: A pure genetic search approach

The economic lot scheduling problem (ELSP) is the challenge of accommodating several products to be produced on a single machine in a cyclical pattern. A solution involves determining the repetitive production schedule for N$N$ products with a goal of minimizing the total of setup and holding costs. We develop the genetic lot scheduling (GLS) procedure. This method combines an extended solution structure with a new item scheduling approach, allowing a greater number of potential schedules to be considered while being the first to explicitly state the assignment of products to periods as part of the solution structure. We maintain efficient solution feasibility determination, a problematic part of ELSP solution generation and a weakness of several other methods, by employing simple but effective sequencing rules that create “nested” schedules. We create a binary chromosomal representation of the new problem formulation and utilize a genetic algorithm to efficiently search for low cost ELSP solutions. The procedure is applied to a benchmark problem suite from the literature, including Bomberger's stamping problem [Bomberger, A dynamic programming approach to a lot scheduling problem. Management Science 1966; 12:778–84], a problem that has been under investigation since the mid 1960's. The genetic lot scheduling procedure produces impressive results, including the best solutions obtained to date on some problems.     

A network-based approach to the multi-activity combined timetabling and crew scheduling problem: Workforce scheduling for public health policy implementation

This paper introduces the multi-activity combined timetabling and crew scheduling problem. The goal of this problem is to schedule the minimum number of workers required in order to successfully visit a set of customers characterized by services needed matched against schedule availability. Two solution strategies are proposed. The first is based on mathematical programming whilst the second uses a heuristic procedure in order to reduce computational time. The proposed model combines timetabling with crew scheduling decisions in one mixed integer programming model which considers multiple activities. The algorithms are tested on randomly generated and real instances provided by the Health to School Initiative, a program based at Bogotá’s local Health Department. The results show that the Initiative can increase its coverage by up to 68% using the proposed heuristic approach as a planning process tool.     

New lower bounds based on column generation and constraint programming for the pattern minimization problem

The pattern minimization problem is a cutting and packing problem that consists in finding a cutting plan with the minimum number of different patterns. This objective may be relevant when changing from one pattern to another involves a cost for setting up the cutting machine. When the minimization of the number of different patterns is done by assuming that no more than the minimum number of rolls can be used, the problem is also referred to as the cutting stock problem with setup costs.     

Converging to periodic schedules for cyclic scheduling problems with resources and deadlines

Cyclic scheduling has been widely studied because of the importance of applications in manufacturing systems and in computer science. For this class of problems, a finite set of tasks with precedence relations and resource constraints must be executed repetitively while maximizing the throughput. Many applications also require that execution schedules be periodic i.e. the execution of each task is repeated with a fixed global period w.The present paper develops a new method to build periodic schedules with cumulative resource constraints, periodic release dates and deadlines. The main idea is to fix the period w, to unwind the cyclic scheduling problem for some number of iterations, and to add precedence relations so that the minimum time lag between two successive executions of any task equals w. Then, using any usual (not cyclic) scheduling algorithm to compute task starting times for the unwound problem, we prove that either the method converges to a periodic schedule of period w or it fails to compute a schedule. A non-polynomial upper bound on the number of iterations to unwind in order to guarantee that cyclic precedence relations and resource constraints are fulfilled is also provided. This method is successfully applied to a real-life problem, namely the software pipelining of inner loops on an embedded VLIW processor core by using a Graham list scheduling algorithm.     

On the complexity of interval scheduling with a resource constraint

We consider a scheduling problem where jobs have to be carried out by parallel identical machines. The attributes of a job j are: a fixed start time s_j, a fixed finish time f_j, and a resource requirement r_j. Every machine owns R units of a renewable resource necessary to carry out jobs. A machine can process more than one job at a time, provided the resource consumption does not exceed R. The jobs must be processed in a non-preemptive way. Within this setting, the problem is to decide whether a feasible schedule for all jobs exists or not.We discuss such a decision problem and prove that it is strongly NP-complete even when the number of resources are fixed to any value R≥2. Moreover, we suggest an implicit enumeration algorithm which has O(nlogn) time complexity in the number n of jobs when the number m of machines and the number R of resources per machine are fixed.The role of storage layout and preemption are also discussed.     

A polynomial algorithm for lot-size scheduling of two type tasks

We study the problem of scheduling unit time tasks of two types on m parallel identical machines. For each type, given numbers of tasks are required to be completed by the specified deadlines. These tasks leave the system at the deadlines. The in-process inventory capacities are given. The objective is to construct a schedule that minimizes the number of changeovers occurring between the tasks of different types. This problem arises, for instance, in the production of gear-boxes on transfer lines and in the tobacco industry. Pattloch and Schmidt [Discrete Appl. Math. 65 (1996) 409-419] give an O(mH) algorithm to solve this problem where H is the latest deadline. We present here a modification of that algorithm with O(Kmin{K,m}) time complexity where K is the number of deadlines.     

Addressing the N/1 scheduling problem—A heuristic approach

The problem of sequencing n-jobs on one machine (n/1) to minimize maximum job lateness has been the subject of much prior research. Most of this research has been directed at identifying optimal solutions to the problem via algorithmic search techniques. A weakness in employing an algorithm for solving the problem, however, is that lengthy computational times may result because of the necessity of searching n! sequences. By employing a multiple heuristic approach this limitation can be avoided. An optimal or near optimal schedule can be identified in a finite number of steps.This paper describes a multiple heuristic model that is effective more than eighty-ninety percent of the time in providing an optimal schedule for the N/l/L max scheduling program. Ten separate heuristics are described, and the results of testing the heuristics over fifteen hundred and sixty randomly generated problems is presented. Three of the heuristics are combined to form the heuristic-scheduling model.     

In situ column generation for a cutting-stock problem

Working with an integer bilinear programming formulation of a one-dimensional cutting-stock problem, we develop an ILP-based local-search heuristic. The ILPs holistically integrate the master and subproblem of the usual price driven pattern-generation paradigm, resulting in a unified model that generates new patterns in situ. We work harder to generate new columns, but we are guaranteed that new columns give us an integer linear-programming improvement (rather then the continuous linear-programming improvement sought by the usual price driven column generation). The method is well suited to practical restrictions such as when a limited number of cutting patterns should be employed, and our goal is to generate a profile of solutions trading off trim loss against the number of patterns utilized. We describe our implementation and results of computational experiments on instances from a chemical-fiber company.     

Row and column generation technique for a multistage cutting stock problem

The multistage cutting stock problem (CSP) generalizes the one-dimensional CSP when a lengthwise cutting process is distributed over two or more successive stages. At every stage of the cutting process incoming rolls are slit into smaller rolls by width. The problem is to minimize total trim loss occurring at all stages of technological process meeting customer demands for finished rolls. We propose a row and column generation technique for solving the multistage one-dimensional CSP. The technique is a generalization of the column generation method suggested by Gilmore and Gomory for solving a classic CSP. The procedure generates only those intermediate rolls (rows) and cutting patterns (columns) that are needed. An auxiliary problem embedded into the frame of the revised simplex algorithm is a non-linear knapsack problem that can be solved efficiently. Computational results prove the overall method is a valuable addition to the tool set for modeling and solving the multistage CSP.Scope and purposeWe investigate a broad class of large-scale linear programming models and suggest a new and efficient way to solve them. The proposed method belongs to a category of decomposition techniques generalizing the famous column generation method. An iteration of the revised simplex algorithm may “enrich” the LP matrix either by generating a new column, as a purely column generation method does, or by generating a combination of a new row and a pair of new columns. The method is a row and column generation technique that we propose and investigate. Applications modeled by a multistage CSP occur in the industries that use a multistage cutting process: paper, leather, film, steel, etc., or a nested packing/loading process: transportation. The unknown variables in the multistage cutting stock problem are intermediate sizes (rows) and cutting patterns (columns). According to the algorithm both are to be generated dynamically. The proposed algorithm brings tremendous benefits in terms of the quality of solutions and computational performance.     

A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers

This paper investigates the hybrid flowshop scheduling with finite intermediate buffers, whose objective is to minimize the sum of weighted completion time of all jobs. Since this problem is very complex and has been proven strongly NP-hard, a tabu search heuristic is proposed. In this heuristic there are two main features. One is that a scatter search mechanism is incorporated to improve the diversity of the search procedure. And the other is that a permutation of N jobs representing their processing order in the first stage instead of a complex complete schedule is used to denote a solution. Computational experiments on randomly generated instances with different structures show that the proposed tabu search heuristic can provide good solutions compared to both the lower bounds and the algorithm proposed for this problem in a lately published literature.     

A cutting plane approach for integrated planning and scheduling

In this paper we propose a branch-and-cut algorithm for solving an integrated production planning and scheduling problem in a parallel machine environment. The planning problem consists of assigning each job to a week over the planning horizon, whereas in the scheduling problem those jobs assigned to a given week have to be scheduled in a parallel machine environment such that all jobs are finished within the week. We solve this problem in two ways: (1) as a monolithic mathematical program and (2) using a hierarchical decomposition approach in which only the planning decisions are modeled explicitly, and the existence of a feasible schedule for each week is verified by using cutting planes. The two approaches are compared with extensive computational testing.     

A DP algorithm for minimizing makespan and total completion time on a series-batching machine

This paper studies a bicriteria scheduling problem on a series-batching machine with objective of minimizing makespan and total completion time simultaneously. A series-batching machine is a machine that can handle up to b jobs in a batch and the completion time of all jobs in a batch is equal to the finishing time of the last job in the batch and the processing time of a batch is the sum of the processing times of jobs in the batch. In addition, there is a constant setup time s for each batch. For the problem we can find all Pareto optimal solutions in O(n²) time by a dynamic programming algorithm, where n denotes the number of jobs.     

Accelerated simulated annealing algorithm applied to the flexible job shop scheduling problem

This paper presents a simulated annealing algorithm accelerated by a partial scheduling mechanism and a cooling schedule mechanism that is a function of the standard deviation. This facilitates a rapid approach to good solutions in the flexible job shop scheduling problem (FJSSP). The results demonstrate that for benchmark instances of several sizes, simulated annealing that implements the proposed mechanism converges more quickly to good solutions than simulated annealing that does not implement the proposed mechanism.     

Review of real-time vehicle schedule recovery methods in transportation services

This paper presents a comprehensive review on methods for real-time schedule recovery in transportation services. The survey concentrates on published research on recovery of planned schedules in the occurrence of one or several severe disruptions such as vehicle breakdowns, accidents, and delays. Only vehicle assignment and rescheduling are reviewed; crew scheduling and passenger logistics problems during disruptions are not. Real-time vehicle schedule recovery problems (RTVSRP) are classified into three classes: vehicle rescheduling, for road-based services, train-based rescheduling, and airline schedule recovery problems. For each class, a classification of the models is presented based on problem formulations and solution strategies. The paper concludes that RTVSRP is a challenging problem that requires quick and good quality solutions to very difficult and complex situations, involving several different contexts, restrictions, and objectives. The paper also identifies research gaps to be investigated in the future, stimulating research in this area.     

A Neural Network Parallel Algorithm for Meeting Schedule Problems

A parallel algorithm for solving meeting schedule problems is presented in this paper where the problem is NP-complete. The proposed system is composed of two maximum neural networks which interact with each other. One is an M × S neural network to assign meetings to available time slots on a timetable where M andS are the number of meetings and the number of time slots, respectively. The other is an M × P neural network to assign persons to the meetings where P is the number of persons. The simulation results show that the state of the system always converges to one of the solutions. Our empirical study shows that the solution quality of the proposed algorithm does not degrade with the problem size.     

An experimental analysis of local minima to improve neighbourhood search

The paper reports the results from a number of experiments on local search algorithms applied to job shop scheduling problems. The main aim was to get insights into the structure of the underlying configuration space. We consider the disjunctive graph representation where the objective function of job shop scheduling is equal to the length of longest paths. In particular, we analyse the number of longest paths, and our computational experiments on benchmark problems provide evidence that in most cases optimal and near optimal solutions do have a small number of longest paths. For example, our best solutions have one to five longest paths only while the maximum number is about sixty longest paths. Based on this observation, we investigate a non-uniform neighbourhood for simulated annealing procedures that gives preference to transitions where a decrease of the number of longest paths is most likely. The results indicate that the non-uniform strategy performs better than uniform methods, i.e. the non-uniform approach has a potential to find better solutions within the same number of transition steps. For example, we obtain the new upper bound 886 on the 20×20 benchmark problem YN1.

Scope and purpose

The paper reports a number of experiments with local search algorithms applied to job shop scheduling (JSS). The JSS problem is defined as follows: Given a number of l jobs, the jobs have to be processed on m machines. Each job consists of a sequence of m tasks, i.e., each task of a job is assigned to a particular machine. The tasks have to be processed during an uninterrupted time period of a fixed length on a given machine. A schedule is an allocation of the tasks to time intervals on the machines and the aim is to find a schedule that minimises the overall completion time which is called the makespan. The scheduling problem is one of the hardest combinatorial optimization problems (cf. M.R. Garey, D.S. Johnson, SIAM J. Comput. 4(4) (1975) 397. Many methods have been proposed to find good approximations of optimum solutions to job shop scheduling problems; for an overview (see E.H.L. Aarts, Local Search in Combinatorial Optimization, Wiley, New York, 1998). In our paper, the main aim is to get insights into the structure of the underlying configuration space. We consider the disjunctive graph representation where the objective function of job shop scheduling is equal to the length of longest paths. In particular, we analyse the number of longest paths, and our computational experiments on benchmark problems provide evidence that in most cases optimal and near optimal solutions do have a small number of longest paths. For example, our best solutions have one to five longest paths only while the maximum number is about sixty longest paths. Based on this observation, we investigate a non-uniform neighbourhood for simulated annealing procedures that gives preference to transitions where a decrease of the number of longest paths is most likely. The results indicate that the non-uniform strategy performs better than uniform methods, i.e., the non-uniform approach has a potential to find better solutions within the same number of transition steps. For example, we obtain the new upper bound 886 on the 20×20 benchmark problem YN1.     

Minimization of earliness, tardiness and due date penalties on uniform parallel machines with identical jobs

We consider a problem of scheduling n identical nonpreemptive jobs with a common due date on m uniform parallel machines. The objective is to determine an optimal value of the due date and an optimal allocation of jobs onto machines so as to minimize a total cost function, which is the function of earliness, tardiness and due date values. For the problem under study, we establish a set of properties of an optimal solution and suggest a two-phase algorithm to tackle the problem. First, we limit the number of due dates one needs to consider in pursuit of optimality. Next, we provide a polynomial-time algorithm to build an optimal schedule for a fixed due date. The key result is an O(m² log m) algorithm that solves the main problem to optimality.Scope and purpose: To extend the existing research on cost minimization with earliness, tardiness and due date penalties to the case of uniform parallel machines.     

Some experiments with a simple tabu search algorithm for the manufacturer's pallet loading problem

The manufacturer's pallet loading problem consists in arranging, orthogonally and without overlapping, the maximum number of boxes with dimensions (l,w) or (w,l) onto a rectangular pallet with dimensions (L,W). This problem has been successfully handled by block heuristics, which generate loading patterns composed by one or more blocks where the boxes have the same orientation. A common feature of such methods is that the solutions provided are limited to the so-called first order non-guillotine patterns. In this paper we propose an approach based on the incorporation of simple tabu search (without longer-term memory structures) in block heuristics. Starting from an initial loading pattern, the algorithm performs moves that increase the size of selected blocks in the current pattern; as a result, other blocks are decreased, eliminated or created. Computational results indicate that the approach is capable of generating superior order optimal patterns for difficult instances reported in the literature.