A bicriteria flowshop scheduling with a learning effect

In many situations, a worker’s ability improves as a result of repeating the same or similar tasks; this phenomenon is known as the learning effect. In this paper the learning effect is considered in a two-machine flowshop. The objective is to find a sequence that minimizes a weighted sum of total completion time and makespan. Total completion time and makespan are widely used performance measures in scheduling literature. To solve this scheduling problem, an integer programming model with n² + 6n variables and 7n constraints where n is the number of jobs is formulated. Because of the lengthy computing time and high computing complexity of the integer programming model, the problem with up to 30 jobs can be solved. A heuristic algorithm and a tabu search based heuristic algorithm are presented to solve large size problems. Experimental results show that the proposed heuristic methods can solve this problem with up to 300 jobs rapidly. According to the best of our knowledge, no work exists on the bicriteria flowshop with a learning effect.     

Notes on “A bicriteria flowshop scheduling with a learning effect”

The aim of this paper is to point out that the integer programming model proposed by Eren and Güner [T. Eren, E. Güner, A bicriteria flowshop scheduling with a learning effect, Applied Mathematical Modelling 32 (2008) 1719–1733] is incorrect. We propose a mixed 0–1 programming model for the same scheduling problem based on their model.     

Tabu search for non-permutation flowshop scheduling problem with minimizing total tardiness

This paper deals with the non-permutation flowshop problem which means that the job sequences are allowed to be different on machines. The objective function is minimizing the total tardiness. Firstly, three mixed-integer linear programming (MILP) models for non-permutation flowshop problems are described, and then are analyzed and assessed their relative effectiveness. Secondly, two Tabu search based algorithms, denoted by LH1 and LH2, are proposed to solve the complicated non-permutation flowshop problems. The algorithms are constructed on specific neighborhood structures which enable the searching method effective. Finally, the performance is evaluated against Taillard’s famous benchmark. Computational experiments show that the proposed algorithms, LH1 and LH2, are significantly superior to the L_TS algorithm. And the percentages of improved permutation flowshop instances by LH1 and LH2 algorithms are about 87.8% and 98.3% with respect to total tardiness, respectively. The non-permutation schedules also have achieved significant improvement in four different scenarios of due dates. Consequently, average percentage improvement (API) is 14.52% for flowshop problems with low tardiness factors. It is evident that exploring non-permutation schedule is effective and necessary for low tardiness factors.     

A tabu search algorithm for the single machine total weighted tardiness problem

In this study, a tabu search (TS) approach to the single machine total weighted tardiness problem (SMTWT) is presented. The problem consists of a set of independent jobs with distinct processing times, weights and due dates to be scheduled on a single machine to minimize total weighted tardiness. The theoretical foundation of single machine scheduling with due date related objectives reveal that the problem is NP-hard, rendering it a challenging area for meta-heuristic approaches. This paper presents a totally deterministic TS algorithm with a hybrid neighborhood and dynamic tenure structure, and investigates the strength of several candidate list strategies based on problem specific characteristics in increasing the efficiency of the search. The proposed TS approach yields very high quality results for a set of benchmark problems obtained from the literature.     

Grasp with memory-based mechanisms for minimizing total tardiness in single machine scheduling with setup times

This paper addresses the problem of scheduling jobs in a single machine with sequence dependent setup times in order to minimize the total tardiness with respect to job due dates. We propose variants of the GRASP metaheuristic that incorporate memory-based mechanisms for solving this problem. There are two mechanisms proposed in the literature that utilize a long-term memory composed of an elite set of high quality and sufficiently distant solutions. The first mechanism consists of extracting attributes from the elite solutions in order to influence the construction of an initial solution. The second one makes use of path relinking to connect a GRASP local minimum with a solution of the elite set, and also to connect solutions from the elite set. Reactive GRASP, which probabilistically determines the degree of randomness in the GRASP construction throughout the iterations, is also investigated. Computational tests for instances involving up to 150 jobs are reported, and the proposed method is compared with heuristic and exact methods from the literature.     

Minimizing the total completion time in a single-machine scheduling problem with a learning effect

This paper introduces a new time-dependent learning effect model into a single-machine scheduling problem. The time-dependent learning effect means that the processing time of a job is assumed to be a function of total normal processing time of jobs scheduled in front of it. In most related studies, the actual job processing time is assumed to be a function of its scheduled position when the learning effect is considered in the scheduling problem. In this paper, the actual processing time of a job is assumed to be proportionate to the length and position of the already scheduled jobs. It shows that the addressed problem remains polynomially solvable for the objectives, i.e., minimization of the total completion time and minimization of the total weighted completion time. It also shows that the shortest processing time (SPT) rule provides the optimum sequence for the addressed problem.     

Minimizing the total completion time on a single machine with the learning effect and multiple availability constraints

This paper considers a single machine scheduling problem with the learning effect and multiple availability constraints that minimizes the total completion time. To solve this problem, a new binary integer programming model is presented, and a branch-and-bound algorithm is also developed for solving the given problem optimally. Since the problem is strongly NP-hard, to find the near-optimal solution for large-sized problems within a reasonable time, two meta-heuristics; namely, genetic algorithm and simulated annealing are developed. Finally, the computational results are provided to compare the result of the binary integer programming, branch-and-bound algorithm, genetic algorithm and simulated annealing. Then, the efficiency of the proposed algorithms is discussed.     

Fast neighborhood search for the single machine total weighted tardiness problem

Most successful heuristics for solving 1||∑w_jT_j are based on swap moves. We present an algorithm which improves the complexity of searching the swap neighborhood from O(n³) to O(n²). We show that this result also improves the complexity of the recently developed dynasearch heuristics.     

Minimizing total tardiness on a single machine with unequal release dates

This study addresses the problem of minimizing total tardiness on a single machine with unequal release dates. Dominance properties established in previous literatures and herein are adopted to develop branch and bound and heuristic procedures. Computational experiments were conducted to evaluate the approaches. The results revealed that the branch and bound algorithm is efficient in solving hard problems and easy problems that involve up to 50 and 500 jobs, respectively. The computational effectiveness of the heuristic is also reported.     

Approximation algorithms for scheduling problems with a modified total weighted tardiness objective

We study the approximability of minimum total weighted tardiness with a modified objective which includes an additive constant. This ensures the existence of a positive lower bound for the minimum value. Moreover the new objective has a natural interpretation in just-in-time production systems.     

Single machine scheduling with exponential sum-of-logarithm-processing-times based learning effect

In this paper we consider the single machine scheduling problems with exponential sum-of-logarithm-processing-times based learning effect. By the exponential sum-of-logarithm-processing-times based learning effect, we mean that the processing time of a job is defined by an exponent function of the sum of the logarithm of the processing times of the jobs already processed. We consider the following objective functions: the makespan, the total completion time, the sum of the quadratic job completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.     

Single machine scheduling with a general exponential learning effect

In this paper we consider the scheduling problem with a general exponential learning effect and past-sequence-dependent (p-s-d) setup times. By the general exponential learning effect, we mean that the processing time of a job is defined by an exponent function of the total weighted normal processing time of the already processed jobs and its position in a sequence, where the weight is a position-dependent weight. The setup times are proportional to the length of the already processed jobs. We consider the following objective functions: the makespan, the total completion time, the sum of the δ ? 0th power of completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.     

具有学习效应的三层供应链排序问题

研究了具有学习效应的三层供应链排序问题. 多个客户分布在不同位置,每个客户都有订 单需要制造商进行生产. 制造商需要针对每一个不同订单的客户从不同的地方进购对应的原材料进行生产,生产完工后需要利用有限的车辆将工件运输到相应客户处. 要求每辆运输车装载尽可 能多的货物才开始运输. 利用动态规划算法研究了最大流程时间、总流程时间以及最大延迟三个目标函数.     

Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance

This paper deals with a single machine scheduling problems with availability constraints. The unavailability of machine results from periodic maintenance activities. In our research, a periodic maintenance consists of several maintenance periods. We consider a machine should stop to maintain after a periodic time interval or to change tools after a fixed amount of jobs processed simultaneously. Each maintenance period is scheduled after a periodic time interval. We study the problems under deterministic environment and flexible maintenance considerations. Preemptive operation is not allowed. In addition, we propose a more reasonable flexible model for the real production settings. The objective is to minimize the makespan. The proposed problem is NP-hard in the strong sense and some heuristic algorithms are provided. The purpose is to present an efficient and effective heuristic algorithm so that it will be straightforward and easy to implement. Computational results show that the proposed algorithm first fit decreasing (DFF) performs well.     

Preemptive scheduling of jobs with agreeable due dates on a single machine to minimize total tardiness

We consider the problem of scheduling n preemptive jobs on a single machine to minimize total tardiness, subject to agreeable due dates, i.e., a later release date corresponds to a later due date. We prove that the problem is -hard in the ordinary sense by showing that it is -hard, and deriving a pseudo-polynomial algorithm for it.     

Comments on “A note on minimizing maximum lateness in an m-machine scheduling problem with a learning effect”

The purpose of this paper is to point out that if there are some machines that do not process any job then the mathematical programming model provided by Eren [T. Eren, A note on minimizing maximum lateness in an m-machine scheduling problem with a learning effect, Applied Mathematics and Computation 209 (2009) 186-190] may not be a valid one. A simple way to fix this problem is given. Furthermore, based on the idea of Eren’s model, a general mathematical programming model is proposed.     

Single machine scheduling with family setups to minimize total earliness and tardiness

This paper considers the problem of scheduling a given number of jobs on a single machine to minimize total earliness and tardiness when family setup times exist. The paper proposes optimal branch-and-bound algorithms for both the group technology assumption and if the group technology assumption is removed. A heuristic algorithm is proposed to solve larger problems with the group technology assumption removed. The proposed algorithms were empirically evaluated on problems of various sizes and parameters. The paper also explores how the choice of procedure affects total earliness and tardiness if an implementation of lean production methods has resulted in a reduction in setup times. An important finding of these empirical investigations is that scheduling jobs by removing the group technology assumption can significantly reduce total earliness and tardiness.     

A bicriteria parallel machine scheduling with a learning effect of setup and removal times

In studies on scheduling problems, generally setup times and removal times of jobs have been neglected or by including those into processing times. However, in some production systems, setup times and removal times are very important such that they should be considered independent from processing times. Since, in general jobs are done according to automatic machine processes in production systems processing times do not differ according to process sequence. But, since human factor becomes influential when setup times and removal times are taken into consideration, setup times will be decreasing by repeating setup processes frequently. This fact is defined with learning effect in scheduling literature. In this study, a bicriteria m-identical parallel machines scheduling problem with a learning effect of setup times and removal times is considered. The objective function of the problem is minimization of the weighted sum of total completion time and total tardiness. A mathematical programming model is developed for the problem which belongs to NP-hard class. Results of computational tests show that the proposed model is effective in solving problems with up to 15 jobs and five machines. We also proposed three heuristic approaches for solving large jobs problems. According to the best of our knowledge, no work exists on the minimization of the weighted sum of total completion time and total tardiness with a learning effect of setup times and removal times.     

Solution of the NP-hard total tardiness minimization problem in scheduling theory

The classical NP-hard (in the ordinary sense) problem of scheduling jobs in order to minimize the total tardiness for a single machine 1‖ΣT _j is considered. An NP-hard instance of the problem is completely analyzed. A procedure for partitioning the initial set of jobs into subsets is proposed. Algorithms are constructed for finding an optimal schedule depending on the number of subsets. The complexity of the algorithms is O(n ²Σp _j ), where n is the number of jobs and p _j is the processing time of the jth job (j = 1, 2, …, n).     

A due-date assignment problem with learning effect and deteriorating jobs

In this paper we consider a single-machine scheduling problem with the effects of learning and deterioration. In this model, job processing times are defined by functions of their starting times and positions in the sequence. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of earliness, tardiness and due-date. We show that the problem remains polynomially solvable under the proposed model.