Search

This work investigates a new semi-online scheduling problem with lookahead. We focus on job scheduling on two identical parallel machines, where deterministic online algorithms only know the information of k initial jobs (i.e., the initial-lookahead information), while the following jobs still arrive one-by-one in an over-list fashion. We consider makespan minimization as the objective. The study aims at revealing the value of knowing k initial jobs, which are used to improve the competitive performance of those online algorithms without such initial-lookahead information. We provide the following findings: (1) For the scenario where the k initial jobs are all the largest jobs with length Δ , we prove that the classical LIST algorithm is optimal with competitive ratio (k + 3) / (k + 2) ; (2) For the scenario where the total length of these k   (> 1) jobs is at least Δ , we show that any online algorithm has a competitive ratio at least 3/2, implying that the initial-lookahead knowledge is powerless since there exists a 3/2-competitive online algorithm without such information; (3) For the scenario where the total length of these k   (> α) jobs is at least α Δ (α ≥ 2), we propose an online algorithm, named as LPT-LIST, with competitive ratio of (α + 2) / (α + 1) , implying that the initial-lookahead information indeed helps to improve the competitiveness of those online algorithms lacking such information. [ABSTRACT FROM AUTHOR]

Under support of industry 4.0, researchers have shown an increased interest in MapReduce scheduling problems to process big data. However, very few studies investigate MapReduce scheduling problems under parallel batch machine environment, which is also common in practice. Motivated by this, we study a parallel batch machine scheduling problem in which all the jobs are belonging to MapReduce type. The objective of the considered problem is of minimizing the total weighted tardiness. For solving this problem, we first establish a mixed integer linear programming model, and then a rule-based genetic algorithm is developed to solve it. Numerical experiments are also conducted to demonstrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

In many manufacturing and service systems, it is of great importance to generate processing schedules with strong response abilities to unexpected or urgent jobs. In this paper, we investigate the problem of scheduling jobs on two parallel identical machines. The objective is to minimise the maximum difference between any two consecutive completion times of jobs, i.e. to minimise the maximum inter-completion time. The processing of any job cannot be interrupted, and a smaller objective value of the processing schedule implies a faster response to an unexpected job that may arrive at any time point. The problem was introduced by Zheng, Pinedo, Lee, Liu, and Xu [2019. "Towards Robustness of Response Times: Minimising the Maximum Inter-completion Time on Parallel Machines." International Journal of Production Research 57 (1): 182–199]. In this work, we first give a sufficient condition of feasible solutions with respect to the makespan constraint, and reveal several basic properties of any optimal solution. We then prove a theoretical lower bound of the objective value, and propose a O (n 2) time algorithm to compute the lower bound. An efficient heuristic algorithm is further constructed to solve the considered problem. Experimental results show that the proposed algorithm outperforms all the three heuristics introduced in Zheng, Pinedo, Lee, Liu, and Xu 2019. [ABSTRACT FROM AUTHOR]

This work investigates an unrelated parallel machine scheduling problem in the shared manufacturing environment. Based on practical production complexity, five job and machine-related factors, including job splitting, setup time, learning effect, processing cost and machine eligibility constraint, are integrated into the considered problem. Parallel machines with uniform speed but non-identical processing capabilities are shared on a sharing service platform, and jobs with different types can only be processed by the machines with matching eligibilities. The platform pays an amount of processing cost for using any machine to process the jobs. To balance the processing cost paid and the satisfaction of customers, we aim to minimize the weighted sum of total processing cost and total completion time of jobs in the considered problem. We establish a mixed integer linear programming model, and provide a lower bound by relaxing the machine eligibility constraint. The CPLEX solver is employed to generate optimal solutions for small-scale instances. For large-scale instances, we propose an efficient heuristic algorithm. Experimental results demonstrate that for various instance settings, the proposed algorithm can always produce near optimal solutions. We further present several managerial insights for the shared manufacturing platform. [ABSTRACT FROM AUTHOR]

Motivated by scheduling practices that require a response to unplanned high-priority jobs as soon as possible without preempting any in-processing jobs, this paper considers a deterministic identical parallel machine scheduling problem to achieve robustness with regard to a worst-case response time. To the best of our knowledge, this paper is the first to study the objective of minimising the maximum inter-completion time, i.e. the maximum time difference between any two consecutive completion times of jobs. For this novel scheduling problem, we first show its NP-hardness, and then propose an integer linear programming formulation and three heuristic approaches. Numerical experiments demonstrate the efficiency of our solution methods. [ABSTRACT FROM AUTHOR]

Motivated by a variety of applications in sharing economy, we study an identical parallel machine scheduling problem with due date-to-deadline window by jointly considering machine sharing and the time value of money. A factory owns a set of parallel identical machines and processes a set of production orders within a finite time period. In the sharing setting, the factory may also rent external machines to handle a part of orders by paying some extra cost. The factory aims to determine the sharing policy of the production orders and the scheduling rule of machines, to maximize its total future value of profits by satisfying the orders. To the best of our knowledge, there are no previous results for this problem. In this work, a mathematical programming model is derived, and a problem-specific genetic algorithm and a heuristic are proposed to solve large-scale instances. Numerical experiments using randomly generated instances are carried out to evaluate the effectiveness and efficiency of the proposed solution methods. [ABSTRACT FROM AUTHOR]

We study multitasking scheduling and due-window assignment problems in a single machine, which can be found in various application domains. In multitasking environment, unfinished job always interrupts in-processing job. In common due window assignment, the aim is to find optimal due window to minimise the value of the earliness and tardiness penalty. In this paper, we study two problems, where the objective of the first problem is minimise the earliness, tardiness, due-window starting time, and due-window size costs, the objective of the second problem is minmax common due-date with completion time penalty, then we obtain some analytical properties and provide polynomial time solutions. Finally, the experimental results show that the proposed methods are effective. [ABSTRACT FROM AUTHOR]

Based on the classical MapReduce concept, we propose an extended MapReduce scheduling model. In the extended MapReduce scheduling problem, we assumed that each job contains an open-map task (the map task can be divided into multiple unparallel operations) and series-reduce tasks (each reduce task consists of only one operation). Different from the classical MapReduce scheduling problem, we also assume that all the operations cannot be processed in parallel, and the machine settings are unrelated machines. For solving the extended MapReduce scheduling problem, we establish a mixed-integer programming model with the minimum makespan as the objective function. We then propose a genetic algorithm, a simulated annealing algorithm, and an L-F algorithm to solve this problem. Numerical experiments show that L-F algorithm has better performance in solving this problem. [ABSTRACT FROM AUTHOR]

This paper investigates the quay crane scheduling problem (QCSP) at container ports, subject to arbitrary precedence constraint among vessel container tasks. Differing from classic machine scheduling problems, noncrossing constraint for quay cranes must be satisfied. This is because quay cranes work in parallel and they travel on a same rail (along the berth), to perform container unloading and loading tasks for vessels. Precedence relation in an arbitrary form is rarely investigated in the literature, however, it may be originated from reefers or dangerous cargo which requires high priority of processing, and yard stacking plan. We present the computational complexity for several problem variations. In particular, we show the QCSP, even without precedence constraint, is strongly NP-hard. This complexity result improves the state-of-the-art, in which the same problem is shown to be NP-hard in the ordinary sense. Besides, we also prove that for two parallel quay cranes, if the processing times of container tasks are ones and twos, then this scheduling problem is NP-hard. This result implies that the QCSP with arbitrary precedence constraint is very difficult to solve. A genetic algorithm is proposed to obtain near-optimal solutions. Computational experiments demonstrate the efficiency. [ABSTRACT FROM AUTHOR]

At a container port, container vessels are served by quay cranes for loading and unloading containers. Each vessel is typically split into bays from head to tail where containers are stored. Parallel quay cranes can process different bays simultaneously, and their processing efficiency significantly affects the turn-around time of a container vessel. Sharing a single traveling rail, the quay cranes cannot crossover each other, and this phenomenon is referred as the non-crossing constraint. In addition, the quay cranes may have different processing speeds due to gradual equipment updates. Inspired by updating activities of cranes in modern container terminals, this paper studies a scheduling problem with two uniform quay cranes, aiming at minimizing the turn-around time of a vessel, i.e., the makespan. We mainly develop an integrated approximation algorithm which is -approximation, where the two quay cranes are of processing speeds 1 and , respectively. [ABSTRACT FROM AUTHOR]

In this paper, we consider the online hierarchical scheduling problem on two parallel machines, with the objective of maximizing the minimum machine load. Since no competitive algorithm exists for this problem, we consider the semi-online version with bounded processing times, in which the processing times are bounded by an interval [ 1 , α ] where α ≥ 1 . We prove that no algorithm can have a competitive ratio less than 1 + α and present an optimal algorithm. Moreover, if we further know the sum of jobs' processing times in advance, we prove that no algorithm can have a competitive ratio less than α where 1 ≤ α < 2 , and propose an α -competitive algorithm for this case. [ABSTRACT FROM AUTHOR]

This paper considers scheduling deteriorating jobs on a single machine with release times and rejection. Deteriorating job means that its actual processing time is a increasing function on its execution starting time. In this situation, jobs can be rejected by paying penalties. Each job is associated with a release time. The objective is to minimize the makespan plus the total penalty incurred by rejecting jobs. We present two dynamic programming algorithms and then design an FPTAS for the considered problem. [ABSTRACT FROM AUTHOR]

We study an online scheduling problem that is motivated by applications such as car-sharing. Users submit ride requests, and the scheduler aims to accept requests of maximum total profit using a single server (car). Each ride request specifies the pick-up time and the pick-up location (among two locations, with the other location being the destination). The scheduler has to decide whether or not to accept a request immediately at the time when the request is submitted (booking time). We consider two variants of the problem with respect to constraints on the booking time: In the fixed booking time variant, a request must be submitted a fixed amount of time before the pick-up time. In the variable booking time variant, a request can be submitted at any time during a certain time interval that precedes the pick-up time. We present lower bounds on the competitive ratio of deterministic and randomized algorithms for both variants and propose a greedy algorithm that achieves the best possible competitive ratio among deterministic algorithms. [ABSTRACT FROM AUTHOR]

Abstract: This paper deals with a parallel machine scheduling problem. Different from fixed processing time assumption in the classical scheduling, a job’s processing time is a simple linear increasing function of its starting time. The aim is makespan minimization, and our focus is on the case with an arbitrary number of parallel machines. We prove that LIST rule is -approximation where is the number of machines and is the maximum deteriorating rate of job. We then propose one heuristic LDR (Largest deteriorating Rate first). The heuristic is proved by -approximation where is the minimum deteriorating rate. We further show that this ratio is tight when and 4. [Copyright &y& Elsevier]

Abstract: Scheduling with past-sequence-dependent () delivery times is motivated by questions that arise in the electronic manufacturing industry: an electronic component may be exposed to certain a electromagnetic field while waiting for processing and is required to neutralize the effect of electromagnetism. The time spent on the neutralization process has been modeled as delivery time in the literature. In this paper, we consider single-machine scheduling problems with delivery times. We respectively derive polynomial algorithms for the following objective functions: the minimization of the total weighted completion time, the total weighted discounted completion time, the total absolute differences in completion times and the sum of earliness, tardiness and common due date penalty. At last, for the criteria of minimization the total weighted tardiness, we propose a polynomial algorithm to optimally solve the problem under a certain condition. [Copyright &y& Elsevier]

Abstract: In this paper we investigate two online scheduling problems. The first one is online scheduling on parallel machines with one machine periodically unavailable. The second problem is online scheduling on two uniform parallel machines where one machine is periodically unavailable. The online paradigm is that jobs arrive over list, i.e., when a job presents, we have to irrevocably assign it before the next one is seen. Preemption is not allowed. The objective is to minimize makespan. We suppose that the length of each available period is normalized to 1 and the length of each unavailable period is . For the first problem, we give an optimal algorithm with competitive ratio 2. For the second problem, we assume that the speed of the periodically unavailable machine is normalized to 1, while the speed of the other one is . In the case where , we design an algorithm and show that it is optimal with competitive ratio . Then we further give some lower bounds on competitive ratio in the case . We also study a special case and prove that algorithm proposed in Xu et al. (2009) is optimal with competitive ratio . [Copyright &y& Elsevier]