Operational fixed job scheduling problem

Download
2004
Türsel Eliiyi, Deniz
In this study, we consider the Operational Fixed Job Scheduling Problem on identical parallel machines. The problem is to select a subset of jobs for processing among a set of available jobs with fixed arrival times and deadlines, so as to maximize the total weight. We analyze the problem under three environments: Working time constraints, Spread time constraints, and Machine dependent job weights. We show that machine eligibility constraints appear as a special case of the last environment. We settle the complexity status of all problems, and show that they are NP-hard in the strong sense and have several polynomially solvable special structures. For all problems, we propose branch and bound algorithms that employ powerful reduction mechanisms and efficient lower and upper bounds. The results of our computational runs reveal that, the algorithms return optimal solutions for problem instances with up to 100 jobs in reasonable solution times.

Suggestions

Spread time considerations in operational fixed job scheduling
Eliiyi, D. T.; Azizoğlu, Meral (Informa UK Limited, 2006-10-15)
In this study, we consider the operational fixed job scheduling problem on identical parallel machines. We assume that the jobs have fixed ready times and deadlines, and spread time constraints are imposed on machines. Our objective is to select a set of jobs for processing so as to maximise the total weight. We show that the problem is strongly NP-hard, and we investigate several special polynomially solvable cases. We propose a branch and bound algorithm that employs size reduction mechanisms, dominance c...
Operational fixed interval scheduling problem on uniform parallel machines
Bekki, Oezguen Baris; Azizoğlu, Meral (Elsevier BV, 2008-04-01)
In this study, we address an operational fixed interval scheduling problem on uniform parallel machines. Our objective is to maximize the total weight of the jobs processed. We show that the problem is NP-hard in the strong sense and develop polynomial time algorithms for some special cases. We propose a branch and bound algorithm that employs dominance conditions and tight bounds. The results of our computational tests have revealed that the algorithm returns optimal solutions for problem instances with up...
A fixed job scheduling problem with machine-dependent job weights
Eliiyi, D. T.; Azizoğlu, Meral (2009-01-01)
This study considers the identical parallel machines operational fixed job scheduling problem with machine-dependent job weights. A job is either processed in a fixed interval or is not processed at all. Our aim is to maximise the total weight of the processed jobs. We show that the problem with machine eligibility constraints resides as a special case of this problem. We identify some special polynomially solvable cases and propose a branch-and-bound (BB) algorithm that employs efficient bounding schemes a...
Parallel-machine rescheduling with machine disruptions
Azizoğlu, Meral (Informa UK Limited, 2005-12-01)
In this study we consider a rescheduling problem on identical parallel machines. The rescheduling is undertaken because of a period of unavailability on one of the machines. We consider the total flow time as an efficiency measure and stability is gauged in terms of the number of jobs processed on different machines in the original and new schedules. We show that all efficient schedules with respect to efficiency and stability measures can be generated in polynomial time.
Ranking units by target-direction-set value efficiency analysis and mixed integer programming
Büyükbaşaran, Tayyar; Köksalan, Murat; Department of Industrial Engineering (2005)
In this thesis, two methods are proposed in order to rank units: Target-direction-set value efficiency analysis (TDSVEA) and mixed integer programming (MIP) technique. Besides its ranking ability based on preferences of a decision maker (DM), TDSVEA, which modifies the targeted projection approach of Value Efficiency Analysis (VEA) and Data Envelopment Analysis (DEA), provides important information to analyzer: targets and distances of units from these targets, proposed input allocations in order to project...
Citation Formats
D. Türsel Eliiyi, “Operational fixed job scheduling problem,” Ph.D. - Doctoral Program, Middle East Technical University, 2004.