Local search and genetic algorithm for the job shop scheduling problem with sequence dependent setup times

The Job Shop Scheduling Problem (JSP) is an example of a combinatorial optimization problem that has interested researchers for several decades. In this paper we confront an extension of this problem called JSP with Sequence Dependent Setup Times (SDST-JSP). The approach extends a genetic algorithm and a local search method that demonstrated to be efficient in solving the JSP. For local search, we have formalized neighborhood structures that generalize three well-know structures defined for the JSP. We have conducted an experimental study across conventional benchmark instances showing that the genetic algorithm exploited in combination with the local search, considering all three neighborhoods at the same time, provides the best results. Moreover, this approach outperforms the current state-of-the-art methods.     

Approximation algorithms for two-machine flow shop scheduling with batch setup times

In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow shop with the objective of minimizing the makespan. Jobs are grouped into batches. A sequence independent batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. Besides its practical interest, this problem is a direct generalization of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algorithm. The problem under investigation is known to be NP-hard. We propose two O(n logn) time heuristic algorithms. The first heuristic, which creates a schedule with minimum total setup time by forcing all jobs in the same batch to be sequenced in adjacent positions, has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed which has an improved worst-case performance ratio of 4/3. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

A two-machine flow shop scheduling problem with controllable job processing times

The paper deals with a two-machine flow shop scheduling problem in which both the sequence of jobs and their processing times are decision variables. It is assumed that the cost of performing a job is a linear function of its processing time, and the schedule cost to be minimized is the total processing cost plus maximum completion time cost. In is shown that the decision form of this problem is NP-complete, even when the processing times on one machine only are controllable and all the processing cost units are identical. Two heuristic methods for solving the problem are proposed and their worst-case analysis is presented.     

Approximation schemes for job shop scheduling problems with controllable processing times

In this paper we study the job shop scheduling problem under the assumption that the jobs have controllable processing times. The fact that the jobs have controllable processing times means that it is possible to reduce the processing time of the jobs by paying a certain cost. We consider two models of controllable processing times: continuous and discrete. For both models we present polynomial time approximation schemes when the number of machines and the number of operations per job are fixed.     

Symmetries in timed continuous Petri nets

The dynamics of timed continuous Petri nets under infinite server semantics can be expressed in terms of a piecewise linear system with polyhedral regions. In this article, Petri nets with symmetries are considered where symmetry is understood as a permutation symmetry of the nodes. We establish connections between the qualitative dynamical behavior of the continuous marking and the symmetries. In particular, it is shown that such a symmetry leads to a permutation of the regions and to equivariant dynamics. This allows us to identify special flow-invariant sets which can be used for reductions to systems of smaller dimension. For general piecewise linear systems with polyhedral regions, it is shown that equivariant dynamics always implies a permutation of the regions.     

Fuzzy job shop scheduling with lot-sizing

This paper deals with a problem of determining lot-sizes of jobs in a real-world job shop-scheduling in the presence of uncertainty. The main issue discussed in this paper is lot-sizing of jobs. A fuzzy rule-based system is developed which determines the size of lots using the following premise variables: size of the job, the static slack of the job, workload on the shop floor, and the priority of the job. Both premise and conclusion variables are modelled as linguistic variables represented by using fuzzy sets (apart from the priority of the job which is a crisp value). The determined lots’ sizes are input to a fuzzy multi-objective genetic algorithm for job shop scheduling. Imprecise jobs’ processing times and due dates are modelled by using fuzzy sets. The objectives that are used to measure the quality of the generated schedules are average weighted tardiness of jobs, the number of tardy jobs, the total setup time, the total idle time of machines and the total flow time of jobs. The developed algorithm is analysed on real-world data obtained from a printing company.     

Fuzzy timed Petri nets — analysis and implementation

In [Z. Ding, H. Bunke, M. Schneider, A. Kandel, Fuzzy timed Petri net — definitions, properties and applications, Math. Comput. Modelling (2005) (in press)], we posed two fuzzy timed Petri Net models. Based on the mark changing rate, they can be classified either as a discrete Fuzzy Timed Petri Net model (discrete-FTPN), or as a continuous Fuzzy Timed Petri Net model (continuous-FTPN). In this paper, we present an algorithm developed to compute reachable states for discrete-FTPN models. We also present properties of the continuous-FTPN model, which are used to describe the system’s behavior. From the investigation presented in this paper, we conclude that it is easier to implement a discrete-FTPN model, but for a theoretical study the continuous-FTPN model is better.     

Cyclic job shop scheduling problems with blocking

A tabu search algorithm for a cyclic job shop problem with blocking is presented. Operations are blocking if they must stay on a machine after finishing when the next machine is occupied by another job. During this stay the machine is blocked for other jobs. For this problem traditional tabu search moves often lead to infeasible solutions. Recovering procedures are developed which construct nearby feasible solutions. Computational results are presented for the approach.     

High-multiplicity cyclic job shop scheduling

We consider the High-Multiplicity Cyclic Job Shop Scheduling Problem. There are two objectives of interest: the cycle time and the flow time. We give several approximation algorithms after showing that a very restricted case is APX-hard.     

Modelling setup times,process batches and transfer batches using activity network logic

The objective of this paper is to demonstrate how modelling ideas and solution procedures, borrowed from the field of generalized resource-constrained project scheduling, can be used to formulate and solve several types of production scheduling problems involving sequence-independent setup times as well as process and transfer batches. The computational results provide useful insight in the trade-offs that do exist between the computational effort required and the size of the process and transfer batches used.     

Single-machine scheduling problems with past-sequence-dependent setup times

This paper studies single-machine scheduling problems with setup times which are proportionate to the length of the already scheduled jobs, that is, with past-sequence-dependent or p-s-d setup times. The following objective functions are considered: the maximum completion time (makespan), the total completion time, the total absolute differences in completion times and a bicriteria combination of the last two objective functions. It is shown that the standard single-machine scheduling problem with p-s-d setup times and any of the above objective functions can be solved in O(nlog n) time (where n is the number of jobs) by a sorting procedure. It is also shown that all of our results extend to a “learning” environment in which the p-s-d setup times are no longer linear functions of the already elapsed processing time due to learning effects.     

A comparison of heuristic algorithms for flow shop scheduling problems with setup times and limited batch size

In this paper, we propose different heuristic algorithms for flow shop scheduling problems, where the jobs are partitioned into groups or families. Jobs of the same group can be processed together in a batch but the maximal number of jobs in a batch is limited. A setup is necessary before starting the processing of a batch, where the setup time depends on the group of the jobs. In this paper, we consider the case when the processing time of a batch is given by the maximum of the processing times of the operations contained in the batch. As objective function we consider the makespan as well as the weighted sum of completion times of the jobs. For these problems, we propose and compare various constructive and iterative algorithms. We derive suitable neighbourhood structures for such problems with batch setup times and describe iterative algorithms that are based on different types of local search algorithms. Except for standard metaheuristics, we also apply multilevel procedures which use different neighbourhoods within the search. The algorithms developed have been tested in detail on a large collection of problems with up to 120 jobs.     

Approaching minimum time control of timed continuous Petri nets

This paper considers the problem of controlling timed continuous Petri nets under infinite server semantics. The proposed control strategy assigns piecewise constant flows to transitions in order to reach the target state. First, by using linear programming, a method driving the system from the initial to the target state through a linear trajectory is developed. Then, in order to improve the time of the trajectory, intermediate states are added by means of bilinear programming. Finally, in order to handle potential perturbations, we develop a closed loop control strategy that follows the trajectory computed by the open loop control by calculating a new state after each time step. The algorithms developed here are applied to a manufacturing system.     

Multi-level lot sizing and job shop scheduling with compressible process times: A cutting plane approach

This paper proposes an integer linear programming formulation for a simultaneous lot sizing and scheduling problem in a job shop environment. Among others, one of our realistic assumptions is dealing with flexible machines which enable the production manager to change their working speeds. Then, a number of valid inequalities are developed based on problem structures. As the valid inequalities can help in reducing the non-optimal parts of the solution space, they are dealt with as some cutting planes. The proposed cutting planes are used to solve the problem in (i) cut-and-branch, and (ii) branch-and-cut approaches. The performance of each cutting plane is investigated with CPLEX 12.2 on a set of randomly-generated test data. Then, some performance criteria are identified and the proposed cutting planes are ranked by TOPSIS method.     

Flexible job shop scheduling with overlapping in operations

In this paper, flexible job shop scheduling problem with a new approach, overlapping in operations, is discussed. In many flexible job shops, a customer demand can be released more than one for each job, where demand determines the quantity of each finished job ordered by a customer. In these models each job has a demand more than one. This assumption is an important and practical issue for many flexible job shops such as petrochemical industries. To consider this assumption, we use a new approach, named overlapping in operations. In this approach, embedded operations of each job can be performed due to overlap considerations in which each operation may be overlapped with the others because of its nature. The overlapping is limited by structural constraints, such as the dimensions of the box to be packed or the capacity of the container used to move the pieces from one machine to the next. Since this problem is well known as NP-Hard class, a hierarchical approach used simulated annealing algorithm is developed to solve large problem instances. Moreover, a mixed integer linear programming (MILP) method is presented. To evaluate the validity of the proposed SA algorithm, the results are compared with the optimal solution obtained with the traditional optimization technique (The Branch and Bound method). The computational results validate the efficiency and effectiveness of the proposed algorithm. Also the computational results show that the overlapping considering can improve the makespan and machines utilization measures. So the proposed algorithm can be applied easily in real factory conditions and for the large size problems and it should thus be useful to both practitioners and researchers.     

Modeling the process of human body iron homeostasis using a variant of timed Petri nets

The body iron homeostasis is one of the most important processes in the human body. This complex process is not fully understood and until recently only some parts of it have been described in the literature. In our recent papers the main part of the process has been described and a model based on Petri net theory has been proposed. However, in this model any time dependencies occurring in the biochemical process have not been taken into account. In the present paper the model is enriched in the way that durations of biochemical reactions composing this process have been included into the model. A variant of Petri net where with each place a time interval is associated has been used in order to describe these dependencies. The time interval associated with a place corresponds to a time lag of biochemical conditions which must be fulfilled in order to enable a biochemical reaction to start.     

Single-machine scheduling with deteriorating jobs and past-sequence-dependent setup times

In many realistic scheduling settings a job processed later consumes more time than the same job processed earlier – this is known as scheduling with deteriorating jobs. Most research on scheduling with deteriorating jobs assumes that the actual processing time of a job is an increasing function of its starting time. Thus a job processed late may incur an excessively long processing time. On the other hand, setup times occur in manufacturing situations where jobs are processed in batches whereby each batch incurs a setup time. This paper considers scheduling with deteriorating jobs in which the actual processing time of a job is a function of the logarithm of the total processing time of the jobs processed before it (to avoid the unrealistic situation where the jobs scheduled late will incur excessively long processing times) and the setup times are proportional to the actual processing times of the already scheduled jobs. Under the proposed model, we provide optimal solutions for some single-machine problems.     

Flow shop scheduling jobs with position-dependent processing times

The paper is devoted to some flow shop scheduling problems, where job processing times are defined by functions dependent on their positions in the schedule. An example is constructed to show that the classical Johnson's rule is not the optimal solution for two different models of the two-machine flow shop scheduling to minimize makespan. In order to solve the makespan minimization problem in the two-machine flow shop scheduling, we suggest Johnson's rule as a heuristic algorithm, for which the worst-case bound is calculated. We find polynomial time solutions to some special cases of the considered problems for the following optimization criteria: the weighted sum of completion times and maximum lateness. Some furthermore extensions of the problems are also shown.     

Lot streaming in the two-machine flow shop with setup times

The lot streaming model can sometimes be analyzed as a variation of the basic flow shop model. In this paper, we consider the lot streaming model with setup times, transfer lots of size one, and makespan objective. We show how to harness existing theory for time lags and setup times in the two-machine flow shop to analyze the lot streaming case. Extensions to more than two machines are also discussed.