No-wait two-machine permutation flow shop scheduling problem with learning effect,common due date and controllable job processing times

We consider a two-machine no-wait permutation flow shop common due date assignment scheduling problem where the processing time of a job is given as a function of its position in the sequence and its amount of resource allocated to this job. The common due date (CON) assignment method means that all the jobs are given a common due date. We need to make a decision on the common due date, resource allocation and the sequence of jobs to minimise total earliness, tardiness, common due date cost and total resource cost. We show that the problem remains polynomially solvable under the proposed model.     

Single machine due-window assignment scheduling with resource-dependent processing times to minimise total resource consumption cost

This paper considers a single-machine scheduling problem involving convex resource-dependent processing times and due-window assignment simultaneously. The goal is to minimise the total resource consumption cost under the constraint that the schedule cost involving earliness, tardiness, window location, window size and makespan does not exceed a given limit for two popular due window assignment methods: the common flow allowance (slack) due window assignment method (referred to SLKW) and the common due window assignment method (referred to CONW). We show that the problem can be solved in polynomial time. Some extensions of the problem are also given.     

Convex resource allocation scheduling in the no-wait flowshop with common flow allowance and learning effect

We study the problem of two-machine no-wait flowshop scheduling with learning effect and convex resource-dependent processing times. Under the condition of the due-date assignment with common flow allowance (i.e. slack (SLK) due-date assignment), we provide a bi-criteria analysis where the first criterion is to minimise the scheduling criteria (i.e. the weighted sum of earliness, tardiness and flow allowance costs), and the second criterion is to minimise the resource consumption cost (i.e. the weighted sum of resource consumption cost). The objective is to determine the optimal job sequence, resource allocations and common (flow allowance) slack time that minimise the three different versions of the two criteria. We prove that these problems can be solved in polynomial time.     

Due date assignment in single machine with stochastic processing times

This paper considers two different due date assignment and sequencing problems in single machine where the processing times of jobs are random variables. The first problem is to minimise the maximum due date so that all jobs are stochastically on time. It is shown that sequencing the jobs in decreasing service level (DSL) order optimally solves the problem. The results are then extended for two special cases of flow shop problem. The other problem is to minimise a total cost function which is a linear combination of three penalties: penalty on job earliness, penalty on job tardiness, and penalty associated with long due date assignment. The assignment of a common due date and distinct due dates are investigated for this problem. It is shown that the optimal sequence for the case of common due date is V-shaped.     

Single-machine due-window assignment scheduling based on common flow allowance,learning effect and resource allocation

This article considers a single-machine due-window assignment scheduling problem based on a common flow allowance (i.e. all jobs have slack due window (SLKW)). We assume that the actual processing time of a job is a function of its position in a sequence (learning effect) and its continuously divisible and non-renewable resource allocation. The problem is to determine the optimal due windows, the optimal resource allocation and the processing sequence simultaneously to minimise costs for earliness, tardiness, the window location, window size, makespan and resource consumption. For a linear or a convex function of the amount of a resource allocated to the job, we provide a polynomial time algorithm, respectively. Some extensions of the problem are also shown.     

SINGLE-MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND EARLINESS,TARDINESS AND COMPLETION TIME PENALTIES

The paper considers the problem of scheduling nindependent and simultaneously available jobs on a single machine, where the job processing times are compressible as a linear cost function. The objective is to find an optimal permutation of the jobs, an optimal due date and the optimal processing times which jointly minimize a cost function consisting of the earliness, tardiness, completion time and compressing costs. It shows that the problem can be solved as an assignment problem.     

Multi-objective fuzzy parallel machine scheduling problems under fuzzy job deterioration and learning effects

This paper investigates a multi-objective parallel machine scheduling problem under fully fuzzy environment with fuzzy job deterioration effect, fuzzy learning effect and fuzzy processing times. Due dates are decision variables for the problem and objective functions are to minimise total tardiness penalty cost, to minimise earliness penalty cost and to minimise cost of setting due dates. Due date assignment problems are significant for Just-in-Time (JIT) thought. A JIT company may want to have optimum schedule by minimising cost combination of earliness, tardiness and setting due dates. In this paper, we compare different approaches for modelling fuzzy mathematical programming models with a local search algorithm based on expected values of fuzzy parameters such as job deterioration effect, learning effect and processing times.     

Scheduling about an unrestricted common due windowwith arbitrary earliness/tardiness penalty rates

We consider the NP-hard problem of scheduling jobs on a single machine about an unrestricted due window to minimize total weighted earliness and tardiness cost. Each job has an earliness penalty rate and a tardiness penalty rate that are allowed to be arbitrary. Earliness or tardiness cost is assessed when a job completes outside the due window, which may be an instant in time or a time increment defining acceptable job completion. In this paper we present properties that characterize the structure of an optimal schedule, present a lower bound, propose a two-step branch and bound algorithm, and report results from a computational experiment. We find that optimal solutions can be quickly obtained for medium-sized problem instances.     

Single-machine earliness–tardiness scheduling with two competing agents and idle time

Two-agent scheduling has gained a lot of research attention recently. Two competing agents who have their own objective functions have to perform their respective set of jobs on one or more shared machines. This study considers a two-agent single-machine earliness and tardiness scheduling problem where jobs have distinct due dates and unforced idleness in between any two consecutive jobs is allowed. The objective is to minimize the total earliness and tardiness of jobs from one agent given that the maximum earliness–tardiness of jobs from the other agent cannot exceed an upper bound. In other words, each job from the second agent has a hard due window, whereas each job from the first agent will incur a penalty if completed either before or after its due date. Two mathematical models of the problem are presented, and several necessary optimality conditions are derived. By exploiting the established dominance properties, heuristic algorithms are developed for the problem. Finally, computational experiments are conducted to assess the models and heuristic procedures.     

Due-window assignment and scheduling with general position-dependent processing times involving a deteriorating and compressible maintenance activity

In this paper, we consider common due-window assignment and scheduling problems with general position-dependent processing times involving deteriorating and compressible maintenance activity on a single machine. Two models associated with maintenance activity are examined in this article, in which the maintenance length is assumed to be either time-dependent and compressible or position-dependent and compressible. The objective is to find jointly the location and size of due-window, position of maintenance as well as resource amount allocated to it, and job sequence to minimise a total cost function based on earliness, tardiness, window location, window size and resource cost. We show that the problem considered in each of the two models’ setting can be optimally solved with polynomial time algorithm by reducing to assignment problem. Finally, two examples are provided to illustrate the solution procedures.     

Parallel-machine scheduling with controllable processing times

We consider a problem of scheduling nindependent and simultaneously available jobs on munrelated parallel machines. The job processing times can be compressed through incurring an additional cost, which is a convex function of the amount of compression. Two problems are formulated as assignment problems, which can be solved inO (n³m + n²m log(nm))time. One is to minimize the total compression cost plus the total flow time. The other is to minimize the total compression cost plus the sum of earliness and tardiness costs.     

Research on scheduling with job-dependent learning effect and convex resource-dependent processing times

We study resource allocation scheduling with job-dependent learning effect on a single machine with or without due date assignment considerations. For a convex resource processing time function, we provide a polynomial time algorithm to find the optimal job sequence, and resource allocations that minimise the schedule criterion (the total compression cost) subject to the constraint that the total compression cost (the schedule criterion) is less than or equal to a fixed amount.     

Single-machine common/slack due window assignment problems with linear decreasing processing times

This paper studies linear non-increasing processing times and the common/slack due window assignment problems on a single machine, where the actual processing time of a job is a linear non-increasing function of its starting time. The aim is to minimize the sum of the earliness cost, tardiness cost, due window location and due window size. Some optimality results are discussed for the common/slack due window assignment problems and two O(n log n) time algorithms are presented to solve the two problems. Finally, two examples are provided to illustrate the correctness of the corresponding algorithms.     

Bicriteria scheduling problems involving job rejection,controllable processing times and rate-modifying activity

This paper addresses the bicriteria scheduling problems with simultaneous consideration of job rejection, controllable processing times and rate-modifying activity on a single machine. A job is either rejected, in which case a rejection penalty will be incurred, or accepted and processed on the machine. The rate-modifying activity is an activity on the machine that changes the processing times of the jobs scheduled after the activity. The processing time of a job scheduled after the rate-modifying activity decreases with a job-dependent factor. The processing time of each job can also be controlled by allocating extra resource which is either a linear or a convex function of the amount of a common continuously divisible resource allocated to the job. The objective is to determine the rejected job set, the accepted job sequence, the time (location) of the rate-modifying activity and the resource allocation that jointly find the trade-off between two criteria, where the first criterion is measured as the sum of total completion time and resource consumption cost while the second criterion is the total rejection cost. We consider four different models for treating the two criteria. The computational complexity status and solution procedures are provided for the problems under consideration.     

Approximation algorithms for common due date assignment and job scheduling on parallel machines

We consider the problem of assigning a common due date to a set of jobs and scheduling the jobs on a set of parallel machines so that the weighted sum of the due date, total earliness, and total tardiness is minimized. A heuristic is developed to solve this problem, and an absolute performance ratio is provided for this heuristic. Another heuristic with a better worst-case performance bound is presented for the case with a zero earliness penalty. A fully polynomial approximation scheme is also developed.     

Single-machine scheduling for minimizing total cost with identical,asymmetrical earliness and tardiness penalties

Costs of flowtime, earliness and tardiness should be incorporated in real production scheduling. This paper constructs a single-machine scheduling model with a common due date to minimize the total cost including an identical, asymmetric earliness-tardiness cost. Several dominance conditions necessary for an optimal schedule are derived. A branch and bound algorithm exploiting the conditions is proposed to find an optimal schedule for an unconstrained version of the scheduling problem. Numerical experiments are demonstrated to show the effectiveness of the proposed method.     

Optimal due date quoting for a risk-averse decision-maker under CVaR

This study investigates a due date quoting problem for a project with stochastic duration, taking the decision-maker’s risk attitude into consideration. The project profit is defined as the difference between the price and the cost that is comprised of production cost and earliness–tardiness penalties. In this situation, the due date determination has to be modelled as a stochastic optimisation due to stochastic duration. Conditional value at risk is thus employed as a performance measure to describe the decision-maker’s risk attitude. In fixed price contract, when the unit production cost is not smaller than the unit penalty on earliness, the optimal due date increases with the increase of the degree of a decision-maker’s risk aversion, the unit penalty on delay, and the decrease of the unit penalty on earliness. Besides, when the price is proportional to the due date and the slope is no bigger than the unit penalty on tardiness, the optimal due date is smaller than the result in fixed price. This is because high price for a short due date encourages a decision-maker to quote a small due date. Further, we compare the optimal due date in different parameter setting where the penalty coefficient of earliness is negative or zero, which means there is reward or no penalty on earliness, respectively. Finally, a case study is conducted to validate the effectiveness and efficiency of the proposed model.     

Multi-agent-based workload control for make-to-order manufacturing

Workload control is a production planning and control concept designed to meet the need of the make-to-order industry. In this paper, a multi-agent workload control methodology that simultaneously addresses due date setting, job release and scheduling is proposed. To be consistent with just-in-time production, the objective of minimizing weighted job earliness and tardiness is used. Two new rules are developed, by introducing a feedback mechanism, to set job due dates dynamically. These two new rules implicitly include job pool times and, thus, eliminate the need to estimate job pool times in the presence of workload control. At the critical norm defined in this paper job release control can reduce average job flowtime and work-in-process inventory, without worsening earliness and tardiness, and lead-time performances. The proposed methodology is implemented in a flexible job shop environment. The computational results indicate that the proposed methodology is very effective for production planning and control in make-to-order companies. In addition, the proposed methodology is extremely fast and can be implemented in real time.